CATS-Nov-14-2014

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 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 additional has to provide additional d_v-p_v flow to v. Fukunaga gives an O(k\log k) ratio for this problem with k 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.

Web Accessibility