Changes

In the offline variant, we give the first non-trivial approximation algorithm for the prize-collecting variant of the problem. In the prize-collecting variant, a penalty is associated with each demand. If the subgraph does not satisfy a demand, we need to pay the penalty of the demand. Our algorithm has a logarithmic approximation ratio which is tight up to a constant factor. Indeed our algorithm simplifies and generalizes the previous results for the prize-collecting node-weighted Steiner tree problem.

In the offline variant, we give the first non-trivial approximation algorithm for the prize-collecting variant of the problem. In the prize-collecting variant, a penalty is associated with each demand. If the subgraph does not satisfy a demand, we need to pay the penalty of the demand. Our algorithm has a logarithmic approximation ratio which is tight up to a constant factor. Indeed our algorithm simplifies and generalizes the previous results for the prize-collecting node-weighted Steiner tree problem.

In the online variant of the Steiner forest problem, we give a randomized O(log^3(n))-competitive algorithm. The competitive ratio is tight to a logarithmic factor. This result improves and generalizes the recent result of Naor et al. which is an O(log^5(n))-competitive algorithm for the Steiner tree problem.

In the online variant of the Steiner forest problem, we give a randomized O(log^3(n))-competitive algorithm. The competitive ratio is tight to a logarithmic factor. This result generalizes the recent result of Naor et al. which is an O(log^3(n))-competitive algorithm for the Steiner tree problem, thus answering one of their open problems.

When restricted to planar graphs (and more generally graphs excluding a fixed minor) we give a deterministic primal-dual algorithm with a logarithmic competitive ratio which is tight to a constant factor.

When restricted to planar graphs (and more generally graphs excluding a fixed minor) we give a deterministic primal-dual algorithm with a logarithmic competitive ratio which is tight to a constant factor.

Joint works with MohammadTaghi Hajiaghayi, Debmalya Panigrahi, and MohammadHossein Bateni

Joint works with MohammadTaghi Hajiaghayi, Debmalya Panigrahi, and MohammadHossein Bateni