BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/543
DTSTAMP:20230914T125928Z
SUMMARY:Sub-logarithmic Approximation for Two Variations of tollbooth Probl
 em
DESCRIPTION:Speaker: Sagnik  Mukhopadhyay\n\nAbstract: \nAbstract: We consi
 der the tollbooth pricing problem where the input is a tree with  nodes an
 d  paths\, also called customers\, with budgets \, . Each customer wants t
 o buy her path if the budget permits\, otherwise she does not buy anything
 . The goal is to come up with a pricing of the edges (non-negative in our 
 cases) such that the revenue collected is maximized. This problem is known
  as tollbooth pricing problem. Several variants of this problem have appea
 red in literature\, all of them turn out to be hard to approximate. Intere
 stingly\, if we restrict the underlying tree to a path\, the problem usual
 ly admits very good approximation (or is even poly-time solvable).\n\nIn t
 his talk\, we will discuss two variants of this problem\, namely\, uniform
  tollbooth problem and unique coverage tollbooth problem. In uniform tollb
 ooth problem\, the budgets of the customers are within a constant factor o
 f each other and in unique coverage problem the budget of each customer as
  well as the pricing of each edges can be either 0 or 1. In other words\, 
 there is a set of edges  with the restriction that each customer can buy a
 t most 1 edge from . In recent work of Cygan et al. (ESA 2012)\, it is sho
 wn that both of these two problems admit a -approximation algorithms.\n\nI
 n this talk we will further restrict the problem and show the results for 
 trees with small diameter. We will also mention how this technique can be 
 extended for arbitrary trees.\n
URL:https://www.tcs.tifr.res.in/web/events/543
DTSTART;TZID=Asia/Kolkata:20141017T140000
DTEND;TZID=Asia/Kolkata:20141017T153000
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR