Sub-logarithmic Approximation for Two Variations of tollbooth Problem

We consider the tollbooth pricing problem where the input is a tree with n nodes and m paths, also called customers, with budgets b_i, i \in [m]. Each customer wants to 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 appeared in literature, all of them turn out to be hard to approximate. Interestingly, if we restrict the underlying tree to a path, the problem usually admits very good approximation (or is even poly-time solvable).

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 X with the restriction that each customer can buy at most 1 edge from X. In recent work of Cygan et al. (ESA 2012), it is shown that both of these two problems admit a \mathcal{O}(\log \log n)-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.