Difference between revisions of "CATS-Mar-29-2013"
| Line 1: | Line 1: | ||
== Title == | == Title == | ||
| − | Improvements | + | Improvements for Prize Collecting Steiner Connectivity Problems |
== Speaker == | == Speaker == | ||
| Line 6: | Line 6: | ||
== Abstract == | == Abstract == | ||
| − | 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. | + | 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. |
| − | + | 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. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
Revision as of 19:55, 30 March 2013
Title[edit]
Improvements for Prize Collecting 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.
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.
