论文标题
半综合加权最小值紧密连接的最佳舍入跨度子图
An Optimal Rounding for Half-Integral Weighted Minimum Strongly Connected Spanning Subgraph
论文作者
论文摘要
在加权最小连接的跨越子图（WMSCS）问题中，我们必须购买跨二弹纸的最低成本连接的最低成本连接。我们表明，WMSCSS的半综合线性程序（LP）解决方案可以有效地以乘以$ 1.5 $的成本为积分解决方案。这个舍入与半融合实例的已知$ 1.5 $完整性差距下限相匹配。更普遍地，我们表明，非零条目至少为$ f> 0 $的LP解决方案可以以$ 2- f $的乘法成本进行四舍五入。
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$.
