Difference between revisions of "CATS-Nov-14-2014"
(Created page with "== Title == The Interesting Behavior of the Source Location Problem == Speaker == Guy Kortsarz == Abstract == In the Source Location problem we are given a graph G(V,E) with...") |
|||
| Line 27: | Line 27: | ||
In the main new version suggested by Fukunaga, there is a | In the main new version suggested by Fukunaga, there is a | ||
| − | "free" flow p(v) for every v \in S. If d_v>p_v, S-v | + | "free" flow p(v) for every v \in S. If d_v>p_v, S-v has to provide additional |
| − | d_v-p_v flow to v. Fukunaga gives an O(k\log k) ratio for this problem | + | d_v-p_v flow to v. Fukunaga gives an O(k\log k) ratio for this problem where k is the largest |
demand. | demand. | ||
I will describe very recent improvements and generalizations | I will describe very recent improvements and generalizations | ||
Latest revision as of 21:36, 6 November 2014
Title[edit]
The Interesting Behavior of the Source Location Problem
Speaker[edit]
Guy Kortsarz
Abstract[edit]
In the Source Location problem we are given a graph G(V,E) with costs on the vertices and capacities on the edges and demand d_v for every v \in V. It is required to select a set S so that for any v \notin S the minimum cut between S and v is at least d_v. For example for capacities 1, it is required that there will be at least d_v edge disjoint paths from S to v for every v \notin v.
I will discuss the interesting behavior of this problem on undirected graphs. If all costs are equal then the problem is polynomial. If all demands are equal the problem is polynomial while if the demands are general and the costs are general the problem is Omega(log n) hard to approximate.
I shall discuss the standard submodular cover algorithm that gives O(log n) ratio for all variants of this problem and countless others.
In the main new version suggested by Fukunaga, there is a "free" flow p(v) for every v \in S. If d_v>p_v, S-v has to provide additional d_v-p_v flow to v. Fukunaga gives an O(k\log k) ratio for this problem where k is the largest demand. I will describe very recent improvements and generalizations of this result (by a very recent paper of Nutov and myself).
We show that the problem is related to Steiner Network with vertex disjoint paths. I shall present a beautiful algorithm by Chuzhoy and Khanna for Steiner Network with disjoint paths.
