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)

Faculty Advisor:

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: http://karthik.ise.illinois.edu/ Microsoft teams link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d For more details please visit: https://www.csa.iisc.ac.in/iisc-msr-seminar/ Hosts: Rahul Madhavan and Rameesh Paul

Speaker Bio:

Host Faculty: