Bots, Bureaucrats, editor
84
edits
Changes
From Theory
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..."
== 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.
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.
