Ghost Value Augmentation for k-Edge Connectivity

Start Date: December 11, 2024
Event Start Time: 11:00 AM
Event End Time: 12:00 PM
Seminar Series: Theoretical Computer Science Seminar
Presenter(s): Nathan Klein - Boston University
Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
Event Additional Info: <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar">https://theory.cs.rutgers.edu/theory_seminar</a></p>
Presentation Type: Stand Alone Presentation
Abstract:
We show that every fractionally k-edge-connected weighted graph (i.e. every solution to the canonical k-edge-connectivity linear program) can be rounded to an integral (k-10)-edge-connected graph of no greater cost.

This implies that for large constant values of k, fractional k-edge-connectivity and integral k-edge-connectivity are essentially the same. As a byproduct of this result, we show that one can produce a (k-10)-edge-connected spanning subgraph (ECSS) of cost no more than the optimal k-ECSS, complementing the existing 2-approximation. This result also implies a 1+O(1/k) approximation for the k-edge-connected multi-subgraph problem (k-ECSM), resolving a conjecture of Pritchard from 2011.

This is joint work with Ellis Hershkowitz and Rico Zenklusen.

Events