Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovász extension and non-smooth convex optimization

ABSTRACT

We consider convex relaxations for combinatorial optimization problems with submodular penalties. The relaxations are obtained very naturally through a novel use of the Lovász extension of a submodular function. We also propose the use of simple and recent algorithms for non-smooth convex optimization due to Nesterov to approximately solve them.

For the uncapacitated facility location problem with submodular penalties we design FPTAS for our relaxation that can be used to design approximation algorithms for the original problem for the metric case. In contrast to previous work of Hayrapetyan et al, our algorithms are fast and simple and do not use the ellipsoid algorithm. We also consider more general set covering problems with submodular costs also introduced by Hayrapetyan et al and submodular function minimization.

The running time dependence on ε of our algorithms is either 1/ε or 1/ε². The slower ones (1/ε²) are very simple. The faster ones (1/ε) are more sophisticated and require that certain projections be easy to solve in the base polytope. These projections can generally be solved using submodular function minimization as a subroutine; however for some important special cases, they can be solved much more efficiently, thus providing the fastest of our algorithms.

REFERENCES

• 1: D. P. Bertsekas. Nonlinear Programming. Athena Scientific, Belmont, Massachusetts, Second Edn., 1999.
• 2: D. Bienstock. Potential Function Methods for Approximately Solving Linear Programming Problems: Theory and Practice. CORE Lecture Series, U. Catholique de Louvain, Belgium, 2001.
• 3: D. Bienstock , G. Iyengar, Solving fractional packing problems in O^ast(1/ε) iterations, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007382]
• 4: F. A. Chudak and V. Eleutério: Improved approximation schemes for linear programming relaxations of combinatorial optimization problems. In IPCO'05, pp. 81--96.
• 5: Moses Charikar , Samir Khuller , David M. Mount , Giri Narasimhan, Algorithms for facility location problems with outliers, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.642-651, January 07-09, 2001, Washington, D.C., United States
• 6: William H Cunningham, On submodular function minimization, Combinatorica, v.5 n.3, p.185-192, 1985 [doi>10.1007/BF02579361]
• 7: S. Fujishige: Lexicographically optimal base of a polymatroid with respect to a weight vector. Mathematics of Operations Research, 5 (1980), pp. 186--196.
• 8: S. Fujishige: Submodular Functions and Optimization (Second Edition). Elsevier, Amsterdam, 2005.
• 9: M. Groetschel, L. Lovász and A. Schrijver: Geometric Algorithms and Combinatorial Optimization, Springer, Berlin, 1988
• 10: Ara Hayrapetyan , Chaitanya Swamy , Éva Tardos, Network design for information networks, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 11: D. S. Hochbaum: Approximation algorithms for the set covering and vertex cover problems, SIAM Journal on Computing, 11 (1982), pp. 555--556.
• 12: Dorit S. Hochbaum , Sung-Pil Hong, About strongly polynomial time algorithms for quadratic optimization over submodular constraints, Mathematical Programming: Series A and B, v.69 n.2, p.269-309, Aug. 25, 1995
• 13: Satoru Iwata , Lisa Fleischer , Satoru Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of the ACM (JACM), v.48 n.4, p.761-777, July 2001 [doi>10.1145/502090.502096]
• 14: Satoru Iwata , Nozomu Zuiki, A network flow approach to cost allocation for rooted trees, Networks, v.44 n.4, p.297-301, December 2004 [doi>10.1002/net.v44:4]
• 15: L. Lovász: Submodular functions and convexity. Mathematical Programming --- The State of the Art (A. Bachem, M. Grötschel, and B. Korte, eds., Springer-Verlag, 1983), pp. 235--257.
• 16: Yu Nesterov, Smooth minimization of non-smooth functions, Mathematical Programming: Series A and B, v.103 n.1, p.127-152, May 2005 [doi>10.1007/s10107-004-0552-5]
• 17: Yu. Nesterov, Excessive Gap Technique in Nonsmooth Convex Minimization, SIAM Journal on Optimization, v.16 n.1, p.235-249, 2005 [doi>10.1137/S1052623403422285]
• 18: Yu. Nesterov: Dual extrapolation and its applications for solving variational inequalities and related problems. CORE Discussion Paper #2003/68, CORE 2003.
• 19: Yu. Nesterov: Primal-dual subgradient methods for convex problems. Technical report, CORE, 2005.
• 20: Yu. Nesterov: Minimizing functions with bounded variation of subgradients. Technical report, CORE, 2005.
• 21: Yu. Nesterov: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, 2003.
• 22: R. T. Rockafellar. Convex analysis. Princeton, NJ: Princeton University Press, 1970.
• 23: Alexander Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory Series B, v.80 n.2, p.346-355, Nov. 2000 [doi>10.1006/jctb.2000.1989]
• 24: David B. Shmoys , Chaitanya Swamy , Retsef Levi, Facility location with Service Installation Costs, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 25: Zoya Svitkina , Éva Tardos, Facility location with hierarchical facility costs, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.153-161, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109576]
• 26: J. Vygen: Approximation algorithms for facility location problems (lecture notes). Report No. 05950-OR, Research Institute for Discrete Mathematics, University of Bonn, 2005.
• 27: 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