Solving Packing Problem with Weaker Block Solvers

16 years 10 days ago

Download www14.informatik.tu-muenchen.de

We study the general packing problem with M constraints. In [Jansen and Zhang, TCS 2002] a c(1 + ε)-approximation algorithm for the general packing problem was proposed. A block solver ABS(p, ε/6, c) with price vector p, given accuracy ε and ratio c is required. In addition, in [Villavicencio and Grigoriadis, Network Optimization (1997)] a (1 + ε)approximation algorithm for standard packing problem and its dual problem was studied, with a block solver ABS(p, ε/10) (i.e., c = 1). In this paper we develop c(1+ε)-approximation algorithms for the general packing problem (or with its dual problem), with only weaker block solvers ABS(p, O(ε ), c) with same structure as in previous algorithms, where ε > ε. For both primal and dual problems we design an algorithm with an ABS(p, ε1/10, c) and ε1 > ε. The bound on the number of iterations is polynomial in M, ε and c. Furthermore we show an algorithm for the primal problem with an ABS(p, ε3/6, c) and ε3 > ε. And the bound...

Hu Zhang

Real-time Traffic