*鹏 张 (山东大学)
标签s-t割问题是来自于系统安全和网络通信等领域的一个NP困难问题。在本报告中,我们证明标签s-t割问题的两个自然的线性规划都有很大的整性间隙,即Omega(m)和Omega(m^{1/3}),在此m是图上边的数目。这意味着使用这两个线性规划的最优解值做为标签s-t割问题最优解值的下界来设计好的近似算法是没有希望的。
Math formula preview: