Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions

Calvin Beideman, Karthekeyan Chandrasekaran, Chandra Chekuri, Chao Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 [5] 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(n1/3/log2 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.

Original languageEnglish (US)
Title of host publication42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022
EditorsAnuj Dawar, Venkatesan Guruswami
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772617
DOIs
StatePublished - Dec 1 2022
Event42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022 - Chennai, India
Duration: Dec 18 2022Dec 20 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume250
ISSN (Print)1868-8969

Conference

Conference42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022
Country/TerritoryIndia
CityChennai
Period12/18/2212/20/22

Keywords

  • Approximation
  • Hypergraphs
  • Representation
  • Submodular Functions

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions'. Together they form a unique fingerprint.

Cite this