BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/37
DTSTAMP:20230914T125907Z
SUMMARY:Connections Between Unique Games and Multicut
DESCRIPTION:Speaker: Nisheeth Vishnoi\nMicrosoft Research Lab\nScientia\n19
 6/36 2nd Main\nSadashivnagar\nBangalore 560 080\n\nAbstract: \nWe demonstr
 ate a close connection between Unique Games and Multicut. In Multicut\, on
 e is given a  network graph  and a  demand graph  on the same vertex set a
 nd the goal is to remove as few edges from the network graph as possible s
 uch that every two vertices connected by a demand edge are separated. On t
 he other hand\, Unique Games is a certain family of constraint satisfactio
 n problems.\n\nIn one direction\, we show that\, at least with respect to 
 current algorithmic techniques\, Multicut is not harder than Unique Games.
  Specifically\, we can adapt most known algorithms for Unique Games to wor
 k for Multicut and obtain new approximation guarantees for Multicut that d
 epend on the maximum degree of the demand graph. This degree plays the sam
 e role as the alphabet size plays in approximation guarantees for Unique G
 ames.\n\nIn the other direction\, we show that Multicut is not easier than
  Unique Games:  We exhibit a reduction from Unique Games to Multicut so th
 at the fraction of edges in the optimal multicut is up to a factor of 2 eq
 ual to the fraction of constraint violated by the optimal assignment for t
 he Unique Games instance. In contrast to the vast majority of Unique Games
  reductions whose analysis relies on Fourier analysis and isoperimetric in
 equalities\, this reduction is simple and the analysis is elementary. Furt
 her\, the maximum degree of the demand graph in the instance produced by t
 he reduction is less than the size of the alphabet size in the Unique Game
 s instance.\n\nOur results rely on a simple but previously unknown charact
 erization of Multicut in terms of L_1 metrics (joint work with David Steur
 er).\n
URL:https://www.tcs.tifr.res.in/web/events/37
DTSTART;VALUE=DATE:20091016
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR