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.

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