BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20221128T120000Z
UID:36e7ea0918e412e676290cba332b9e31-363
DTSTAMP:19700101T120011Z
DESCRIPTION:Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/363/approximate-representation-of-symmetric-submodular-functions-via-hypergraph-cut-functions/
SUMMARY: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
DTSTART:20221128T120000Z
END:VEVENT
END:VCALENDAR