- D-405 (D-Block Seminar Room)
In this talk, we will discuss two variants of this problem, namely, uniform tollbooth problem and unique coverage tollbooth problem. In uniform tollbooth problem, the budgets of the customers are within a constant factor of 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 at most 1 edge from . In recent work of Cygan et al. (ESA 2012), it is shown that both of these two problems admit a -approximation algorithms.
In 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.