BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/985
DTSTAMP:20230914T125945Z
SUMMARY:Hardness of Approximation via a Variant of Equivalence of  Optimiza
 tion and Separation Problem
DESCRIPTION:Speaker: Gunjan Kumar\n\nAbstract: \nAbstract: The equivalence 
 of optimization and separation is a widely used tool. The reduction from o
 ptimization to separation is particularly useful for\, e.g.\, solving line
 ar programs with exponential constraints. There are many variants of this 
 equivalence\, one such is the equivalence of weak validity and weak member
 ship. We use this equivalence to show a hardness of approximation for Cove
 rage Norm Extension problem.\n\nIn this problem\, we are given $n$ points 
 and a partial function value at these points. The goal is to find the mini
 mum L_1 distance of the partial function from a coverage function. If F de
 notes the sum of the values of partia function values then clearly an addi
 tive F-approximatio algorithm exist. We show that it is NP-hard to approxi
 mate with a quantity sublinear in F.\n\nThis is a joint work with Umang Bh
 askar.\n
URL:https://www.tcs.tifr.res.in/web/events/985
DTSTART;TZID=Asia/Kolkata:20190816T171500
DTEND;TZID=Asia/Kolkata:20190816T184500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR