Document Open Access Logo

New Query Lower Bounds for Submodular Function Minimization

Authors Andrei Graur, Tristan Pollner, Vidhya Ramaswamy, S. Matthew Weinberg

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2020.64.pdf
  • Filesize: 0.52 MB
  • 16 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Submodular optimization and polymatroids
Keywords
  • submodular functions
  • query lower bounds
  • min cut

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We consider submodular function minimization in the oracle model: given black-box access to a submodular set function f:2^[n] → ℝ, find an element of arg min_S {f(S)} using as few queries to f(⋅) as possible. State-of-the-art algorithms succeed with Õ(n²) queries [Yin Tat Lee et al., 2015], yet the best-known lower bound has never been improved beyond n [Nicholas J. A. Harvey, 2008]. 
We provide a query lower bound of 2n for submodular function minimization, a 3n/2-2 query lower bound for the non-trivial minimizer of a symmetric submodular function, and a binom{n}{2} query lower bound for the non-trivial minimizer of an asymmetric submodular function. 
Our 3n/2-2 lower bound results from a connection between SFM lower bounds and a novel concept we term the cut dimension of a graph. Interestingly, this yields a 3n/2-2 cut-query lower bound for finding the global mincut in an undirected, weighted graph, but we also prove it cannot yield a lower bound better than n+1 for s-t mincut, even in a directed, weighted graph.

Cite As Get BibTex

Andrei Graur, Tristan Pollner, Vidhya Ramaswamy, and S. Matthew Weinberg. New Query Lower Bounds for Submodular Function Minimization. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ITCS.2020.64

Author Details

Andrei Graur
  • Department of Mathematics, Princeton University, Princeton, NJ, USA
Tristan Pollner
  • Department of Mathematics, Princeton University, Princeton, NJ, USA
Vidhya Ramaswamy
  • Department of Computer Science, Princeton University, Princeton, NJ, USA
S. Matthew Weinberg
  • Department of Computer Science, Princeton University, Princeton, NJ, USA

Funding

  • Weinberg, S. Matthew: Supported by NSF CCF-1717899.

References

  1. Yuri Boykov, Olga Veksler, and Ramin Zabih. Fast Approximate Energy Minimization via Graph Cuts. IEEE Trans. Pattern Anal. Mach. Intell., 23(11):1222-1239, 2001. URL: https://doi.org/10.1109/34.969114.
  2. Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. Subquadratic Submodular Function Minimization. CoRR, abs/1610.09800, 2016. URL: http://arxiv.org/abs/1610.09800.
  3. William H. Cunningham. On submodular function minimization. Combinatorica, 5(3):185-192, 1985. URL: https://doi.org/10.1007/BF02579361.
  4. Lisa Fleischer and Satoru Iwata. Improved algorithms for submodular function minimization and submodular flow. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 107-116, 2000. URL: https://doi.org/10.1145/335305.335318.
  5. Martin Grötschel, László Lovász, and Alexander Schrijver. The Ellipsoid Method and its Consequences in Combinatorial Optimization. Combinatorica, 1(2):169-197, 1981. Google Scholar
  6. Nicholas J. A. Harvey. Matchings, matroids and submodular functions. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 2008. URL: http://hdl.handle.net/1721.1/44416.
  7. Satoru Iwata. A Faster Scaling Algorithm for Minimizing Submodular Functions. SIAM J. Comput., 32(4):833-840, 2003. URL: https://doi.org/10.1137/S0097539701397813.
  8. Satoru Iwata, Lisa Fleischer, and Satoru Fujishige. A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM, 48(4):761-777, 2001. URL: https://doi.org/10.1145/502090.502096.
  9. Satoru Iwata and James B. Orlin. A simple combinatorial algorithm for submodular function minimization. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 1230-1237, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496903.
  10. Leonid G. Khachiyan. A Polynomial Algorithm in Linear Programming. Soviet Mathematics Doklady, 20(1):191-194, 1979. Google Scholar
  11. Pushmeet Kohli, M. Pawan Kumar, and Philip H. S. Torr. P3 & Beyond: Move Making Algorithms for Solving Higher Order Functions. IEEE Trans. Pattern Anal. Mach. Intell., 31(9):1645-1656, 2009. URL: https://doi.org/10.1109/TPAMI.2008.217.
  12. Pushmeet Kohli and Philip HS Torr. Dynamic graph cuts and their applications in computer vision. In Computer Vision, pages 51-108. Springer, 2010. Google Scholar
  13. Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1049-1065, 2015. URL: https://doi.org/10.1109/FOCS.2015.68.
  14. Hui Lin and Jeff A. Bilmes. Optimal Selection of Limited Vocabulary Speech Corpora. In INTERSPEECH 2011, 12th Annual Conference of the International Speech Communication Association, Florence, Italy, August 27-31, 2011, pages 1489-1492, 2011. URL: http://www.isca-speech.org/archive/interspeech_2011/i11_1489.html.
  15. James B. Orlin. A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization. In Integer Programming and Combinatorial Optimization, 12th International IPCO Conference, Ithaca, NY, USA, June 25-27, 2007, Proceedings, pages 240-251, 2007. URL: https://doi.org/10.1007/978-3-540-72792-7_19.
  16. Maurice Queyranne. Minimizing symmetric submodular functions. Math. Program., 82:3-12, 1998. URL: https://doi.org/10.1007/BF01585863.
  17. Aviad Rubinstein, Tselil Schramm, and S. Matthew Weinberg. Computing Exact Minimum Cuts Without Knowing the Graph. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, pages 39:1-39:16, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.39.
  18. Alexander Schrijver. A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time. J. Comb. Theory, Ser. B, 80(2):346-355, 2000. URL: https://doi.org/10.1006/jctb.2000.1989.
  19. Jens Vygen. A note on Schrijver’s submodular function minimization algorithm. J. Comb. Theory, Ser. B, 88(2):399-402, 2003. URL: https://doi.org/10.1016/S0095-8956(02)00047-3.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact