BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/470
DTSTAMP:20230914T125925Z
SUMMARY:Sparsest Cut in Bounded Treewidth Graphs
DESCRIPTION:Speaker: Anupam Gupta (Carnegie Mellon University\nDepartment o
f Computer Science\n7203 Gates Building\nPittsburg\, PA 15213\nUnited Stat
es of America)\n\nAbstract: \nAbstract: We consider approximation algorith
ms for the sparsest cut graph partitioning problem. Here\, given graphs G
with demand pairs $\\{s_i\,t_i\\}$\, the goal is to separate G into two pa
rts to minimize the ratio of the number of edges cut to the number of dema
nd pairs separated.\nIn this talk\, I will sketch:\n- the best hardness-of
-approximation (based on P!=NP) currently known for this problem\,\n- and
a 2-approximation algorithm with running time $n^{O(k)}$\, where $k$ is th
e treewidth of the underlying graph G. Our algorithm rounds a Sherali-Adam
s LP relaxation.\nThis positive result can be complemented by (a) an integ
rality gap of a factor of 2 for the Sherali-Adams hierarchy even after pol
ynomially\nmany rounds\, and (b) an unique-games hardness of a factor of 2
. Time permitting\, I will give a high-level intuition of how the NP-hardn
ess\ncan be extended to prove these matching results.\nI will try to keep
the talk as self-contained as possible (this is joint work with Kunal Talw
ar (Microsoft Research SVC) and David Witmer (CMU)\, and appeared at the S
TOC 2013 conference).\n
URL:https://www.tcs.tifr.res.in/web/events/470
DTSTART;TZID=Asia/Kolkata:20140305T160000
DTEND;TZID=Asia/Kolkata:20140305T170000
LOCATION:AG-69
END:VEVENT
END:VCALENDAR