Approximating submodular functions everywhere

ABSTRACT

Submodular functions are a key concept in combinatorial optimization. Algorithms that involve submodular functions usually assume that they are given by a (value) oracle. Many interesting problems involving submodular functions can be solved using only polynomially many queries to the oracle, e.g., exact minimization or approximate maximization.

In this paper, we consider the problem of approximating a non-negative, monotone, submodular function f on a ground set of size n everywhere, after only poly(n) oracle queries. Our main result is a deterministic algorithm that makes poly(n) oracle queries and derives a function f such that, for every set S, f(S) approximates f(S) within a factor α(n), where α(n) = √n+1 for rank functions of matroids and α(n), = O(√n log n) for general monotone submodular functions. Our result is based on approximately finding a maximum volume inscribed ellipsoid in a symmetrized polymatroid, and the analysis involves various properties of submodular functions and polymatroids.

Our algorithm is tight up to logarithmic factors. Indeed, we show that no algorithm can achieve a factor better than Ω(√n/log n), even for rank functions of a matroid.

REFERENCES

• 1: N. Alon and J. Spencer. "The Probabilistic Method". Wiley, second edition, 2000.
• 2: Arash Asadpour , Amin Saberi, An approximation algorithm for max-min fair allocation of indivisible goods, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250808]
• 3: A. Assad and W. Xu. "The Quadratic Minimum Spanning Tree Problem". Naval Research Logistics, 39, 1992.
• 4: K. Ball. "An Elementary Introduction to Modern Convex Geometry". Flavors of Geometry, MSRI Publications, 1997.
• 5: R. G. Bland, D. Goldfarb and M. J. Todd. "The Ellipsoid Method: A Survey". Operations Research, 29, 1981.
• 6: Shahar Dobzinski , Michael Schapira, An improved approximation algorithm for combinatorial auctions with submodular bidders, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1064-1073, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109675]
• 7: J. Edmonds, "Matroids and the Greedy Algorithm", Mathematical Programming, 1, 127--136, 1971.
• 8: K. Fan, "On a theorem of Weyl concerning the eigenvalues of linear transformations, II", Proc. Nat. Acad. Sci., 1950.
• 9: Uriel Feige , Vahab S. Mirrokni , Jan Vondrak, Maximizing Non-Monotone Submodular Functions, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.461-471, October 21-23, 2007 [doi>10.1109/FOCS.2007.40]
• 10: S. Fujishige, "Submodular Functions and Optimization", volume 58 of Annals of Discrete Mathematics. Elsevier, second edition, 2005.
• 11: D. Golovin, "Max-Min Fair Allocation of Indivisible Goods". Technical Report CMU-CS-05-144, 2005.
• 12: M. Grötschel, L. Lovász, and A. Schrijver, "Geometric Algorithms and Combinatorial Optimization", Springer Verlag, second edition, 1993.
• 13: O. Güler and F. Gürtina, "The extremal volume ellipsoids of convex bodies, their symmetry properties, and their determination in some special cases", arXiv:0709.707v1.
• 14: 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]
• 15: Satoru Iwata , James B. Orlin, A simple combinatorial algorithm for submodular function minimization, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1230-1237, January 04-06, 2009, New York, New York
• 16: F. John. "Extremum problems with inequalities as subsidiary conditions", Studies and Essays, presented to R. Courant on his 60th Birthday, January 8, 1948, Interscience, New York, 187--204, 1948.
• 17: Leonid G. Khachiyan, Rounding of polytopes in the real number model of computation, Mathematics of Operations Research, v.21 n.2, p.307-320, May 1996 [doi>10.1287/moor.21.2.307]
• 18: S. Khot, R. Lipton, E. Markakis and A. Mehta. "Inapproximability results for combinatorial auctions with submodular utility functions", WINE, 92--101, 2005.
• 19: Subhash Khot , Ashok Kumar Ponnuswami, Approximation Algorithms for the Max-Min Allocation Problem, Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, August 20-22, 2007, Princeton, NJ, USA [doi>10.1007/978-3-540-74208-1_15]
• 20: P. Kumar and E. A. Yildirim, "Minimum-Volume Enclosing Ellipsoids and Core Sets", Journal of Optimization Theory and Applications, 126, 1--21, 2005.
• 21: B. Lehmann, D. J. Lehmann and N. Nisan. "Combinatorial auctions with decreasing marginal utilities", Games and Economic Behavior, 55, 270--296, 2006.
• 22: J. K. Lenstra , D. B. Shmoys , É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming: Series A and B, v.46 n.3, p.259-271, February 1990 [doi>10.1007/BF01585745]
• 23: L. Lovász, "Submodular Functions and Convexity", in A. Bachem et al., eds, Mathematical Programmming: The State of the Art, 235--257, 1983.
• 24: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 25: Kazuo Murota, Discrete Convex Analysis: Monographs on Discrete Mathematics and Applications 10, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
• 26: H. Narayanan, "Submodular Functions and Electrical Networks", Elsevier, 1997.
• 27: G. L. Nemhauser, L. A. Wolsey and M. L. Fisher. "An analysis of approximations for maximizing submodular set functions I". Mathematical Programming, 14, 1978.
• 28: A. Schrijver, "Combinatorial Optimization: Polyhedra and Efficiency". Springer, 2004.
• 29: 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]
• 30: J. Spencer, "Six Standard Deviations Suffice", Trans. Amer. Math. Soc., 289, 679--706, 1985.
• 31: Peng Sun , Robert M. Freund, Computation of Minimum-Volume Covering Ellipsoids, Operations Research, v.52 n.5, p.690-706, Sep. - Oct. 2004 [doi>10.1287/opre.1040.0115]
• 32: Zoya Svitkina , Lisa Fleischer, Submodular Approximation: Sampling-based Algorithms and Lower Bounds, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.697-706, October 25-28, 2008 [doi>10.1109/FOCS.2008.66]
• 33: M. J. Todd. "On Minimum Volume Ellipsoids Containing Part of a Given Ellipsoid". Math of OR, 1982.
• 34: Jan Vondrak, Optimal approximation for the submodular welfare problem in the value oracle model, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374389]
• 35: L. A. Wolsey. "An Analysis of the Greedy Algorithm for the Submodular Set Covering Problem". Combinatorica, 2, 385--393, 1982.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms