TY - GEN
T1 - Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions
AU - Beideman, Calvin
AU - Chandrasekaran, Karthekeyan
AU - Chekuri, Chandra
AU - Xu, Chao
N1 - Publisher Copyright:
© Calvin Beideman, Karthekeyan Chandrasekaran, Chandra Chekuri, and Chao Xu; licensed under Creative Commons License CC-BY 4.0.
PY - 2022/12/1
Y1 - 2022/12/1
N2 - 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.
AB - 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.
KW - Approximation
KW - Hypergraphs
KW - Representation
KW - Submodular Functions
UR - http://www.scopus.com/inward/record.url?scp=85144302042&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85144302042&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.FSTTCS.2022.6
DO - 10.4230/LIPIcs.FSTTCS.2022.6
M3 - Conference contribution
AN - SCOPUS:85144302042
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022
A2 - Dawar, Anuj
A2 - Guruswami, Venkatesan
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022
Y2 - 18 December 2022 through 20 December 2022
ER -