Minimum Label s-t Cut has Large Integrality Gaps
Minimum Label s-t Cut has Large Integrality Gaps
复制标题
DOI：
10.1016/j.ic.2020.104543
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
Peng Zhang;Linqing Tang
中科院分区：
文献类型：
--
作者：
Peng Zhang;Linqing Tang
最小标号s-t割问题是组合优化中的一个基本问题。这个问题来自于真实的世界中的许多应用，例如信息安全和计算机网络。本文研究了两个关于最小标号s-t割的线性规划，证明了这两个线性规划都有很大的积分间隙，即Ω（m）和Ω（m1/3− Ω），其中m是问题的输入图中的边数，Ω> 0是任意小的常数.由于最小标号s-t割是NP-难的，而线性规划技术是设计逼近算法的主要方法，我们的结果给了否定的答案，希望可以找到更好的最小标号s-t割的逼近算法设计，纯粹依赖于线性规划.
Abstract The Min Label s-t Cut problem is a fundamental problem in combinatorial optimization. This problem comes from many applications in real world, for example, information security and computer networks. We study two linear programs for Min Label s-t Cut, proving that both of them have large integrality gaps, namely, Ω (m) and Ω (m 1/3− ϵ) for the respective linear programs, where m is the number of edges in the input graph of the problem and ϵ> 0 is any arbitrarily small constant. As Min Label s-t Cut is NP-hard and the linear programming technique is a main approach to design approximation algorithms, our results give negative answer to the hope that designs can be found for better approximation algorithms for Min Label s-t Cut that purely rely on linear programming.