1,721,147 research outputs found
A new linear storage, polynomial-time approximation scheme for the subset-sum problem
No full textAbstractGiven a set of positive integers, the Subset-Sum Problem is to find that subset whose sum is closest to, without exceeding, a given W. For this problem, we present a polynomial-time approximation scheme requiring only a linear storage, and prove that its worst-case performance dominates that of the linear-storage approximation schemes from the literature. A modification of the scheme requiring linear time and space for any fixed bound ε on the relative error, is also given. Extensive computational results on randomly generated test problems are reported
Clique tree inequalities define facets of the asymmetric traveling salesman polytope
No full textAbstractThis paper solves, in the affermative, the open question of whether the Grötschel-Pulleyblank clique tree inequalities define facets of the asymmetric traveling salesman polytope and its monotonization. This generalizes the corresponding result for symmetric polytopes. The proof makes use of a new recursive definition of clique tree, based on induction on the number of its “teeth” rather than of its “handles”
- …
