| Autor: |
Hershkowitz, D Ellis, Kehne, Gregory, Ravi, R. |
| Rok vydání: |
2020 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
In the weighted minimum strongly connected spanning subgraph (WMSCSS) problem we must purchase a minimum-cost strongly connected spanning subgraph of a digraph. We show that half-integral linear program (LP) solutions for WMSCSS can be efficiently rounded to integral solutions at a multiplicative $1.5$ cost. This rounding matches a known $1.5$ integrality gap lower bound for a half-integral instance. More generally, we show that LP solutions whose non-zero entries are at least a value $f > 0$ can be rounded at a multiplicative cost of $2 - f$. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
