[home] - [up] |

Lectures and Colloquia during the semester

Humboldt-Universität zu Berlin

Rudower Chaussee 5

12489 Berlin

Room 3.101 - map -

*Abstract: *
Given a graph with weights or costs associated to the edges, the
Steiner tree problem is to find the minimum cost subtree connecting a
given set of *k* vertices. For general graphs this problem is
NP-complete. As with other combinatorial optimization problems it is
interesting, and relevant for practical applications, to consider not
worst case instances, but random instances. The simplest and most
natural random example is to take a complete graph on *n* vertices
where the edge costs are independent exponentials with mean 1. We
show that for any *2 \le k=o(n)* the minimum cost tree connecting *k*
given vertices has cost asymptotic to *(k-1/n)(log n-log k)*.

Two special cases of this problem have been studied previously: Davis
and Prieditis and Janson found the minimum cost of a path connecting
two given vertices (the case *k=2*) and Frieze the minimum cost of a
spanning tree (*k=n*).
In both cases there is a polynomial time algorithm whose behaviour on
the random graph can be analyzed to obtain the result. For general *k*
this is not the case and different methods must be used.
A corollary of our result is that
whenever *k=o(n)* an asymptotically optimal spanning tree can be found
in polynomial time.

All new results described are joint work with Béla Bollobás, David Gamarnik and Benny Sudakov.

** Colloquium - 16 Uhr s.t.**

*Abstract: *
We study the approximability of dense and sparse instances of the following
problems: the minimum 2-edge-connected (*2*-EC) and 2-vertex-connected (*2*-VC) spanning
subgraph, metric TSP with distances *1* and *2* (TSP(1,2)), maximum path packing, and
the longest path (cycle) problems. The approximability of dense instances of these problems
was left open in a paper of Arora *et al.* (1995). We resolve the approximability of
these problems by proving tight upper (approximation algorithms) and lower bounds
(inapproximability). We prove that *2*-EC, *2*-VC and TSP(1,2) problems are Max-SNP-hard,
even on *3*-regular graphs, and provide explicit hardness constants, under the usual
*P \not = NP* assumption. We also improve the approximation ratio for *2*-EC and *2*-VC
on graphs with maximum degree *3*. These are the first known explicit hardness results
on sparse and dense graphs for some of these problems. We also apply our results to prove
bounds on the integrality gaps of LP relaxations for *2*-EC and TSP(1,2) dense and sparse
problems, related to the metric TSP conjecture, due to Goemans (1995).

This is joint work with Bela Csaba and Marek Karpinski.

[home] - [up] - [top]