McGill University - School of Computer Science

Algorithms Seminar

Everybody is welcome.

DATE:	Wednesday, March 15th
TIME:	4:30 PM - 5:30 PM
PLACE:	McConnell 320
TITLE:	Approximability of the Minimum-Cost k-Connected Spanning Subgraph Problem
SPEAKER:	Artur Czumaj, New Jersey Institute of Technology

In the first part of the presentation I will describe polynomial-time approximation schemes (PTAS) for several basic minimum-cost multi-connectivity problems in geometrical graphs. I describe a randomized approximation scheme for finding a biconnected graph spanning a set of points in a multi-dimensional Euclidean space and having the expected total cost within $(1+\epsilon)$ of the optimum. For any constant dimension and $\epsilon$, the scheme runs in time $O(n \log n)$. It can be turned into Las Vegas one without affecting its asymptotic time complexity, and also efficiently derandomized.

Further, I will briefly explain the extension of this approach to a PTAS for finding a minimum-cost k-edge connected graph/multigraph spanning a set of points in a multi-dimensional Euclidean space and to a PTAS for the problem of Euclidean minimum-cost Steiner biconnectivity.

In the second part of the talk I will discuss hardness of approximations for the minimum-cost k-vertex- and k-edge-connected spanning subgraph problems. The only inapproximability result known so far states that the k-edge-connectivity problem in unweighted graphs does not have a PTAS unless P=NP, even for k=2. I shall present a simpler proof of this result that holds even for graphs of bounded degree, and provide the first proof that finding a PTAS for the k-vertex-connectivity problem in unweighted graphs is NP-hard even for k=2 and for graphs of bounded degree.

This is a joint work Andrzej Lingas (Lund University, Sweden)

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at cgm-help@cgm.cs.mcgill.ca.