|
|
 |
|
Jeudi 16 Avril
| Heure: |
10:30 - 12:00 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Approximation Schemes for Planar Graph Connectivity Problems |
| Description: |
Meike Neuwohner The k-Edge-Connected Subgraph problem and the k-Connectivity Augmentation problem are among the most basic Network Design problems and, consequently, have been heavily studied. Due to their approximation hardness, the gold standard in terms of approximation guarantee are
strong constant factors. Interestingly, this approximation hardness does not carry over to planar graphs. In particular, the 2-Edge-Connected Subgraph problem admits a PTAS on planar graphs. However, the used techniques are very different from the celebrated Bakers framework, which is a standard way to design PTASs for planar graphs. The main obstacle of using Bakers technique in its classical form is that it requires a certain locality of the problem. However, k-edge/vertex-connectivity are global properties. We present a novel, and arguably clean, way to extend Bakers framework to deal with larger connectivity requirements. Based on this, we obtain a PTAS for the k-Edge-Connected Subgraph problem and its vertex analog, even with costs, as long as the max-to-min cost ratio is bounded by a constant. Moreover, together with further insights, we obtain a PTAS for the k-Connectivity Augmentation problem in the same cost setting. We complement this with an NP-hardness result for planar augmentation, showing that all our results are essentially tight.
This is joint work with Vera Traub and Rico Zenklusen. |
|
|
