Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions

Authors Calvin Beideman, Karthekeyan Chandrasekaran, Chandra Chekuri, Chao Xu



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2022.6.pdf
  • Filesize: 0.62 MB
  • 18 pages

Document Identifiers

Author Details

Calvin Beideman
  • University of Illinois, Urbana-Champaign, IL, USA
Karthekeyan Chandrasekaran
  • University of Illinois, Urbana-Champaign, USA
Chandra Chekuri
  • University of Illinois, Urbana-Champaign, USA
Chao Xu
  • University of Electronic Science and Technology of China, Chengdu, China

Cite AsGet BibTex

Calvin Beideman, Karthekeyan Chandrasekaran, Chandra Chekuri, and Chao Xu. Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FSTTCS.2022.6

Abstract

Submodular functions are fundamental to combinatorial optimization. Many interesting problems can be formulated as special cases of problems involving submodular functions. In this work, we consider the problem of approximating symmetric submodular functions everywhere using hypergraph cut functions. Devanur, Dughmi, Schwartz, Sharma, and Singh [Devanur et al., 2013] showed that symmetric submodular functions over n-element ground sets cannot be approximated within (n/8)-factor using a graph cut function and raised the question of approximating them using hypergraph cut functions. Our main result is that there exist symmetric submodular functions over n-element ground sets that cannot be approximated within a o(n^{1/3}/log² n)-factor using a hypergraph cut function. On the positive side, we show that symmetrized concave linear functions and symmetrized rank functions of uniform matroids and partition matroids can be constant-approximated using hypergraph cut functions.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • Submodular Functions
  • Hypergraphs
  • Approximation
  • Representation

Metrics

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

References

  1. A. Badanidiyuru, S. Dobzinski, H. Fu, R. Kleinberg, N. Nisan, and T. Roughgarden. Sketching valuation functions. In Proceedings of the 23rd annual ACM-SIAM Symposium on Discrete algorithms, SODA, pages 1025-1035, 2012. Google Scholar
  2. M-F. Balcan, N. Harvey, and S. Iwata. Learning symmetric non-monotone submodular functions. In NIPS Workshop on Discrete Optimization in Machine Learning, NIPS, 2012. Google Scholar
  3. M-F. Balcan and Nicholas JA Harvey. Submodular functions: Learnability, structure, and optimization. SIAM Journal on Computing, 47(3):703-754, 2018. Google Scholar
  4. Y. Chen, S. Khanna, and A. Nagda. Near-linear size hypergraph cut sparsifiers. In Proceedings of the IEEE 61st Annual Symposium on Foundations of Computer Science, pages 61-72, 2020. Google Scholar
  5. N. Devanur, S. Dughmi, R. Schwartz, A. Sharma, and M. Singh. On the Approximation of Submodular Functions. Preprint in arXiv: 1304.4948v1, 2013. Google Scholar
  6. V. Feldman and J. Vondrák. Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas. SIAM Journal on Computing, 45(3):1129-1170, 2016. Google Scholar
  7. S. Fujishige. Submodular functions and optimization. Elsevier, 2005. Google Scholar
  8. M. Goemans, N. Harvey, S. Iwata, and V. Mirrokni. Approximating submodular functions everywhere. In Proceedings of the 20th annual ACM-SIAM Symposium on Discrete algorithms, SODA, pages 535-544, 2009. Google Scholar
  9. T. Helgason. Aspects of the theory of hypermatroids. In Hypergraph Seminar, pages 191-213. Springer, 1974. Google Scholar
  10. A. Schrijver. Combinatorial optimization: polyhedra and efficiency. Springer Science & Business Media, 2003. Google Scholar
  11. C. Seshadri and J. Vondrák. Is submodularity testable. Algorithmica, 69(1):1-25, 2014. Google Scholar
  12. Z. Svitkina and L. Fleischer. Submodular Approximation: Sampling-based Algorithms and Lower Bounds. SIAM Journal on Computing, 40(6):1715-1737, 2011. Google Scholar
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