skip to main content
10.5555/1496770.1496829guideproceedingsArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
research-article
Free access

Approximating submodular functions everywhere

Published: 04 January 2009 Publication History

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]
A. Asadpour and A. Saberi. "An approximation algorithm for max-min fair allocation of indivisible goods". STOC, 114--121, 2007.
[3]
A. Assad and W. Xu. "The Quadratic Minimum Spanning Tree Problem". Naval Research Logistics, <b>39</b>, 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, <b>29</b>, 1981.
[6]
S. Dobzinski and M. Schapira. "An improved approximation algorithm for combinatorial auctions with submodular bidders". SODA, 1064--1073, 2006.
[7]
J. Edmonds, "Matroids and the Greedy Algorithm", Mathematical Programming, <b>1</b>, 127--136, 1971.
[8]
K. Fan, "On a theorem of Weyl concerning the eigenvalues of linear transformations, II", Proc. Nat. Acad. Sci., 1950.
[9]
U. Feige, V. Mirrokni and J. Vondrák, "Maximizing non-monotone submodular functions", FOCS, 461--471, 2007.
[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]
S. Iwata, L. Fleischer, and S. Fujishige, "A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions", Journal of the ACM, <b>48</b>, 761--777, 2001.
[15]
S. Iwata and J. Orlin, "A Simple Combinatorial Algorithm for Submodular Function Minimization", SODA, 2009.
[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]
L. G. Khachiyan. "Rounding of polytopes in the real number model of computation", Math of OR, <b>21</b>, 307--320, 1996.
[18]
S. Khot, R. Lipton, E. Markakis and A. Mehta. "Inapproximability results for combinatorial auctions with submodular utility functions", WINE, 92--101, 2005.
[19]
S. Khot and A. Ponnuswami. "Approximation Algorithms for the Max-Min Allocation Problem". APPROX-RANDOM, 204--217, 2007.
[20]
P. Kumar and E. A. Yildirim, "Minimum-Volume Enclosing Ellipsoids and Core Sets", Journal of Optimization Theory and Applications, <b>126</b>, 1--21, 2005.
[21]
B. Lehmann, D. J. Lehmann and N. Nisan. "Combinatorial auctions with decreasing marginal utilities", Games and Economic Behavior, <b>55</b>, 270--296, 2006.
[22]
J. K. Lenstra, D. B. Shmoys and E. Tardos. "Approximation algorithms for scheduling unrelated parallel machines". Mathematical Programming, <b>46</b>, 259--271, 1990.
[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]
J. Matoušek, "Lectures on Discrete Geometry". Springer, 2002.
[25]
K. Murota, "Discrete Convex Analysis", SIAM Monographs on Discrete Mathematics and Applications, SIAM, 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, <b>14</b>, 1978.
[28]
A. Schrijver, "Combinatorial Optimization: Polyhedra and Efficiency". Springer, 2004.
[29]
A. Schrijver, "A combinatorial algorithm minimizing submodular functions in strongly polynomial time", Journal of Combinatorial Theory, Series B, 80, 346--355, 2000.
[30]
J. Spencer, "Six Standard Deviations Suffice", Trans. Amer. Math. Soc., <b>289</b>, 679--706, 1985.
[31]
P. Sun and R. M. Freund. "Computation of Minimum Volume Covering Ellipsoids", Operations Research, <b>52</b>, 690--706, 2004.
[32]
Z. Svitkina and L. Fleischer. "Submodular Approximation: Sampling-Based Algorithms and Lower Bounds". FOCS, 2008.
[33]
M. J. Todd. "On Minimum Volume Ellipsoids Containing Part of a Given Ellipsoid". Math of OR, 1982.
[34]
J. Vondrák. "Optimal Approximation for the Submodular Welfare Problem in the Value Oracle Model". STOC, 2008.
[35]
L. A. Wolsey. "An Analysis of the Greedy Algorithm for the Submodular Set Covering Problem". Combinatorica, <b>2</b>, 385--393, 1982.

Cited By

View all
  • (2022)Neural estimation of submodular functions with applications to differentiable subset selectionProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3601690(19537-19552)Online publication date: 28-Nov-2022
  • (2018)Approximating the nash social welfare with budget-additive valuationsProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175455(2326-2340)Online publication date: 7-Jan-2018
  • (2018)Team Performance with Test ScoresACM Transactions on Economics and Computation10.1145/32746446:3-4(1-26)Online publication date: 23-Oct-2018
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image Guide Proceedings
SODA '09: Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms
January 2009
1297 pages

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 04 January 2009

Qualifiers

  • Research-article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)61
  • Downloads (Last 6 weeks)19
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2022)Neural estimation of submodular functions with applications to differentiable subset selectionProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3601690(19537-19552)Online publication date: 28-Nov-2022
  • (2018)Approximating the nash social welfare with budget-additive valuationsProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175455(2326-2340)Online publication date: 7-Jan-2018
  • (2018)Team Performance with Test ScoresACM Transactions on Economics and Computation10.1145/32746446:3-4(1-26)Online publication date: 23-Oct-2018
  • (2018)On (1, $$\epsilon $$∈)-Restricted Max---Min Fair Allocation ProblemAlgorithmica10.1007/s00453-018-0407-880:7(2181-2200)Online publication date: 1-Jul-2018
  • (2017)Local aggregative gamesProceedings of the 31st International Conference on Neural Information Processing Systems10.5555/3295222.3295286(5347-5357)Online publication date: 4-Dec-2017
  • (2017)Verifying Reliability Properties Using the Hyperball Abstract DomainACM Transactions on Programming Languages and Systems10.1145/315601740:1(1-29)Online publication date: 19-Dec-2017
  • (2017)Approximate modularity revisitedProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055476(1028-1041)Online publication date: 19-Jun-2017
  • (2017)The limitations of optimization from samplesProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055406(1016-1027)Online publication date: 19-Jun-2017
  • (2017)Faster and Simpler Sketches of Valuation FunctionsACM Transactions on Algorithms10.1145/303987113:3(1-9)Online publication date: 6-Mar-2017
  • (2017)Approximation Algorithms for Maximin Fair DivisionProceedings of the 2017 ACM Conference on Economics and Computation10.1145/3033274.3085136(647-664)Online publication date: 20-Jun-2017
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media