A fast approximation scheme for fractional covering problems with variable upper bounds

ABSTRACT

We present the first combinatorial approximation scheme for mixed positive packing and covering linear programs that yields a pure approximation guarantee. Our algorithm returns solutions that simultaneously satisfy general positive covering constraints and packing constraints that are variable upper bounds. The returned solution has positive linear objective function value at most 1 + ε times the optimal value.Our approximation scheme is based on Lagrangian-relaxation methods. Previous such approximation schemes for mixed packing and covering problems does not simultaneously satisfy packing and covering constraints exactly. We show how to exactly satisfy general positive covering constraints simultaneously with variable upper bounds.A natural set of problems that our work addresses are linear programs for various network design problems: generalized Steiner network, vertex connectivity, directed connectivity, capacitated network design, group Steiner forest. These are all NP-hard problems for which there are approximation algorithms that round the solution to the corresponding linear program. Solving the linear program is often the computational bottleneck in these problems, and thus a fast approximation scheme for the LP relaxation means faster approximation algorithms.For the special case of survivable network design, we introduce a new modification of the push-relabel maximum flow algorithm that allows us to perform each iteration in amortized O(m + n log n) time, instead of one maximum flow per iteration that is implied by the straight forward adaptation of our general algorithm. (m is the number of edges and n is the number of vertices in the network.) In conjunction with an observation that reduces the number of iterations to {log n for f0} constraint matrices, the modification allows us to obtain an algorithm that is faster than existing exact or approximate algorithms by a factor of at least O(m) and by a factor of O(m log n) if the number of demand pairs is Ω(n).

REFERENCES

• 1: D. Bienstock. Experiments with a network design algorithm using ε-approximate linear programs. Submitted for publication, 1996.
• 2: D. Bienstock. Approximately solving large-scale linear programs. i. strengthening lower bounds and accelerating convergence. Technical report, CORC Report 1999-1, Columbia University, 1999. Extended abstract: Proc. 11th Ann. ACM-SIAM Symposium on Discrete Algorithms, January 2000.
• 3: D. Bienstock. Potential function algorithms for approximately solving linear programs: theory and practice. CORE Lecture Series monograph. 2001. Available from Center for Operations Research and Econometrics (CORE), U. Catholique de Louvain, Belgium.
• 4: Robert D. Carr , Lisa K. Fleischer , Vitus J. Leung , Cynthia A. Phillips, Strengthening integrality gaps for capacitated network design and covering problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.106-115, January 09-11, 2000, San Francisco, California, United States
• 5: Joseph Cheriyan , Santosh Vempala , Adrian Vetta, Approximation algorithms for minimum-cost k-vertex connected subgraphs, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509955]
• 6: B. V. Cherkassky. A fast algorithm for computing maximum flow in a network. In A. V. Karzanov, editor, Collected Papers: Combinatorial Methods for Flow Problems, volume 3, pages 90--96. The Institute for Systems Studies, Moscow, 1979. In Russian.
• 7: B. V. Cherkassky. A fast algorithm for constructing a maximum flow through a network. In Selected topics in discrete mathematics (Moscow, 1972--1990), number 158 in Amer. Math. Soc. Transl. Ser. 2, pages 23--30. Amer. Math. Soc., Providence, RI, 1994.
• 8: B. V. Cherkassky and A. V. Goldberg. On implementing the push-relabel method for the maximum flow problem. Algorithmica, 19:390--410, 1997.
• 9: U. Derigs and W. Meier. Implementing goldberg's max-flow-algorithm---a computational investigation. Z. Oper. Res., 33(6):383--403, 1989.
• 10: Lisa K. Fleischer, Approximating Fractional Multicommodity Flow Independent of the Number of Commodities, SIAM Journal on Discrete Mathematics, v.13 n.4, p.505-520, Oct. 2000 to Nov. 2000 [doi>10.1137/S0895480199355754]
• 11: Lisa Fleischer, A 2-Approximation for Minimum Cost {0, 1, 2} Vertex Connectivity, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.115-129, June 13-15, 2001
• 12: K. Jain, An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.339, October 14-17, 2001
• 13: Naveen Garg , Rohit Khandekar, Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.500, November 16-19, 2002
• 14: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 15: Naveen Garg , Goran Konjevod , R. Ravi, A polylogarithmic approximation algorithm for the group Steiner tree problem, Journal of Algorithms, v.37 n.1, p.66-84, Oct. 2000 [doi>10.1006/jagm.2000.1096]
• 16: Andrew V. Goldberg , Jeffrey D. Oldham , Serge A. Plotkin , Clifford Stein, An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flow, Proceedings of the 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.338-352, June 22-24, 1998
• 17: Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
• 18: R. E. Gomory and T. C. Hu. Multi-terminal network flows. J. Soc. Indust. Appl. Math, 9:551--570, 1961.
• 19: M. D. Grigoriadis and L. G. Khachiyan. Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM Journal on Optimization, 4:86--107, 1994.
• 20: Michael D. Grigoriadis , Leonid G. Khachiyan, Coordination complexity of parallel price-directive decomposition, Mathematics of Operations Research, v.21 n.2, p.321-340, May 1996 [doi>10.1287/moor.21.2.321]
• 21: Dan Gusfield, Very simple methods for all pairs network flow analysis, SIAM Journal on Computing, v.19 n.1, p.143-155, Feb. 1990 [doi>10.1137/0219009]
• 22: 42nd Annual Symposium on Foundations of Computer Science, 2001.
• 23: K. Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1):39--60, 2001.
• 24: George Karakostas, Faster approximation schemes for fractional multicommodity flow problems, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.166-173, January 06-08, 2002, San Francisco, California
• 25: David Karger , Serge Plotkin, Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.18-25, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225073]
• 26: Philip Klein , Serge Plotkin , Clifford Stein , Eva Tardos, Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts, SIAM Journal on Computing, v.23 n.3, p.466-487, June 1994 [doi>10.1137/S0097539792241175]
• 27: Tom Leighton , Fillia Makedon , Serge Plotkin , Clifford Stein , Éva Tardos , Spyros Tragoudas, Fast approximation algorithms for multicommodity flow problems, Journal of Computer and System Sciences, v.50 n.2, p.228-243, April 1995
• 28: Vardges Melkonian , Éva Tardos, Approximation Algorithms for a Directed Network Design Problem, Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.345-360, June 09-11, 1999
• 29: Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research, v.20 n.2, p.257-301, May 1995 [doi>10.1287/moor.20.2.257]
• 30: Tomasz Radzik, Fast deterministic approximation for the multicommodity flow problem, Mathematical Programming: Series A and B, v.78 n.1, p.43-58, July 1, 1997 [doi>10.1007/BF02614505]
• 31: Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
• 32: David Paul Williamson, On the design of approximation algorithms for a class of graph problems, Massachusetts Institute of Technology, Cambridge, MA, 1993
• 33: Neal E. Young, Randomized rounding without solving the linear program, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.170-178, January 22-24, 1995, San Francisco, California, United States
• 34: N. Young, Sequential and Parallel Algorithms for Mixed Packing and Covering, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.538, October 14-17, 2001