BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20221128T120000Z
UID:821a22ac8dc68f044999f39a2e580bad-364
DTSTAMP:19700101T120011Z
DESCRIPTION:Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/364/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.

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://csa.iisc.ac.in/theoryseminars/


Hosts: Rahul Madhavan and Rameesh Paul
DTSTART:20221128T120000Z
END:VEVENT
END:VCALENDAR