Seminars

View all Seminars  |  Download ICal for this event

Approximate 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.

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