Difference between revisions of "CATS-Mar-29-2013"
| Line 10: | Line 10: | ||
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 | + | 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 | ||
Revision as of 03:55, 22 March 2013
Title[edit]
Improvements on Offline and Online Node-Weighted Steiner Connectivity Problems
Speaker[edit]
Vahid Liaghat, University of Maryland
Abstract[edit]
Consider a graph G=(V,E) with a weight value w(v) associated with each vertex v. A demand is a pair of vertices (s,t). A subgraph H satisfies the demand if s and t are connected in H. In the (offline) node-weighted Steiner forest problem, given a set of demands the goal is to find the minimum-weight subgraph H which satisfies all demands. In the online variant, the demands arrive one by one and we need to satisfy each demand immediately; without knowing the future demands.
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 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.
Joint works with MohammadTaghi Hajiaghayi, Debmalya Panigrahi, and MohammadHossein Bateni
