Seminars
View all Seminars | Download ICal for this eventApproximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions
Series: Bangalore Theory Seminars
Speaker: Karthekeyan Chandrasekaran University of Illinois, Urbana-Champaign
Date/Time: Nov 28 11:00:00
Location: CSA Seminar Hall (Room No. 254, First Floor)
Abstract:
Submodular functions are fundamental to combinatorial optimization. We consider the problem of approximating symmetric submodular functions everywhere using hypergraph cut functions. Prior works have shown that symmetric submodular functions over n-element ground sets cannot be approximated within a (n/8)-factor using a graph cut function and raised the question of approximating them using hypergraph cut functions. In this talk, I will show that there exist symmetric submodular functions over n-element ground sets that cannot be approximated within a o(n^{1/3}/log^2 n)-factor using a hypergraph cut function. On the positive side, I will discuss the approximability of symmetrized concave linear functions and symmetrized rank functions of uniform matroids and partition matroids using hypergraph cut functions.
Organizers Note:: Based on joint work with Calvin Beideman, Chandra Chekuri, and Chao Xu.
Speaker Website: Link
Microsoft teams link:
Link
For more details please visit: Link
Hosts: Rahul Madhavan and Rameesh Paul