• Calendar

November 8, Tuesday
12:00 – 14:00

Let $G=(V,E)$ be a graph and let $S$ be a subset of $V$. The $S$-connectivity $\lambda_S(u,v;G)$ of $u$ and $v$ in $G$ is the maximum number of $uv$-paths that no two of them have an edge or a node in $S-{u,v}$ in common. We consider the following problem on undirected graphs:

Connectivity Augmentation Problem (CAP): Instance: A graph $G=(V,E)$, a node subset $S \subseteq V$, and an integer requirement function $r(u,v)$ on $V \times V$. Objective: Add a minimum size set $F$ of new edges to $G$ so that $\lambda_S(u,v;G+F) \geq r(u,v)$ for all $u,v \in V$.

Three extensively studied particular choices of $S$ are: the edge-CAP ($S=\emptyset$), the node-CAP ($S=V$), and the element-CAP ($r(u,v)=0$ whenever $u \in S$ or $v \in S$). A polynomial algorithm for edge-CAP was developed by Andras Frank. We consider the element-CAP and the node-CAP, that are NP-hard even for $r(u,v) \in \{0,2\}$.

We show a $7/4$-approximation algorithm for the element-CAP, improving the previously best known $2$-approximation. The approximation ratio is based on a new lower bound on the number of edges needed to cover a skew-supermodular set function.

For the node-CAP we establish an approximation threshold indicating that the node-CAP is unlikely to have a polylogarithmic approximation.

If the time a allows I will also describe a tight $O(\log n)$-approximation for arbitrary $S \neq V$ (this part is a joint work with Guy Kortsarz).

Bio:
Education:D.Sc. Applied Mathematics, Technion, Haifa, Israel
Postdocs:
1. Dept. of Combinatorics and Optimization, Univ. of Waterloo, Canada
2. Max-Planck-Institute fur Informatik, Saarbrucken, Germany.
Since March 2000: Lecturer at the CS Dept. at the Open University of Israel.
Since Nov. 2004: Chair of the CS Dept. at the Open University of Israel.

FIELDS OF INTEREST:
Approximation and exact algorithms, hardness of approximation; network design, connectivity augmentation, feedback set problems, cover and packing problems, scheduling problems, facility location problems,Combinatorial Optimization, Combinatorics, Graph Theory.