Parallel Approximation and Integer Programming Reformulation

Simple item page
dc.creatorPataki, Gabor
dc.creatorTural, Mustafa
dc.date2008-07-21
dc.date.accessioned2026-07-07T09:52:01Z
dc.date.available2026-07-07T09:52:01Z
dc.descriptionWe show that in a knapsack feasibility problem an integral vector $p$, which is short, and near parallel to the constraint vector gives a branching direction with small integer width. We use this result to analyze two computationally efficient reformulation techniques on low density knapsack problems. Both reformulations have a constraint matrix with columns reduced in the sense of Lenstra, Lenstra, and Lovász. We prove an upper bound on the integer width along the last variable, which becomes 1, when the density is sufficiently small. In the proof we extract from the transformation matrices a vector which is near parallel to the constraint vector $a.$ The near parallel vector is a good branching direction in the original knapsack problem, and this transfers to the last variable in the reformulations.
dc.identifierhttps://arxiv.org/abs/0807.3355
dc.identifierhttp://arxiv.org/abs/0807.3355
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/165449
dc.subjectOptimization and Control
dc.subjectCombinatorics
dc.subject9008, 52C07, 11H06
dc.titleParallel Approximation and Integer Programming Reformulation
dc.typetext

Files

Collections

arXiv