TY - JOUR
T1 - An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph
AU - Hershkowitz, D. Ellis
AU - Kehne, Gregory
AU - Ravi, R.
N1 - Publisher Copyright:
© 2020 The Author(s)
PY - 2021/4
Y1 - 2021/4
N2 - 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.
AB - 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.
KW - Approximation algorithms
KW - Integrality gap
KW - Minimum strongly connected spanning subgraph
KW - Network design
UR - https://www.scopus.com/pages/publications/85096139024
U2 - 10.1016/j.ipl.2020.106067
DO - 10.1016/j.ipl.2020.106067
M3 - Article
AN - SCOPUS:85096139024
SN - 0020-0190
VL - 167
JO - Information Processing Letters
JF - Information Processing Letters
M1 - 106067
ER -