An Improved Integrality Gap for the Calinescu-Karloff-Rabani Relaxation for Multiway Cut

机译：用于多道切割的CalineCu-Karloff-Rabani弛豫的完整性差距

获取原文

页面导航

摘要
著录项
相似文献
相关主题

摘要

We construct an improved integrality gap instance for the Calinescu-Karloff-Rabani LP relaxation of the Multiway Cut problem. For k ≥ 3 terminals, our instance has an integrality ratio of 6/(5+ 1/k-1)-ε, for every constant ε > 0. For every k ≥ 4, this improves upon a longstanding lower bound of 8/(7 + 1/k-1) by Freund and Karloff [7]. Due to the result by Manokaran et al. [9], our integrality gap also implies Unique Games hardness of approximating Multiway Cut of the same ratio.

机译：我们为多道切割问题的CalineCu-Karloff-Rabani LP放松构建一个改进的完整性差距实例。对于k≥3端子，我们的实例具有6 /（5+ 1 / k-1）-ε的整体比，每个常数ε> 0.对于每个k≥4，这改善了8 /的长期下限（7 + 1 / k-1）由Freund和Karloff [7]。由于Manokaran等人的结果。 [9]，我们的完整性差距还意味着近似多道比例的近似比例的独特游戏硬度。

著录项

来源
《International Conference on Integer Programming and Combinatorial Optimization》|2017年|456p|共12页
会议地点
作者
Haris Angelidakis; Yury Makarychev; Pasin Manurangsi;
展开▼
作者单位

展开▼
会议组织
原文格式 PDF
正文语种
中图分类 TP301-53;
关键词

相似文献

外文文献
中文文献
专利

1. A lower bound of 8/(7＋1:k-1) on the integrality ratio of the Calinescu-Karloff-Rabani relaxation for multiway cut [J] . Ari Freund, Howard Karloff Information Processing Letters . 2000,第1a2期

机译：Calinescu-Karloff-Rabani松弛多向切割的积分比的下限8 /（7 + 1：k-1）
2. Improving the integrality gap for multiway cut [J] . Berczi Kristof, Chandrasekaran Karthekeyan, Kiraly Tamas, Mathematical Programming . 2020,第1a2期

机译：提高多道切割的完整性差距
3. A lower bound of 8/(7＋(1:k-1) on the the itnergrality ratio of the Calinescu-Karloff-Rabani relaxation for multiay cut [J] . Air Freund, Howard Karloff Information Processing Letters . 2000,第1a2期

机译：Calinescu-Karloff-Rabani弛豫的多倍剪切的迭代率的下限8 /（7＋（1：k-1）
4. An Improved Integrality Gap for the Calinescu-Karloff-Rabani Relaxation for Multiway Cut [C] . Haris Angelidakis, Yury Makarychev, Pasin Manurangsi International conference on integer programming and combinatorial optimization . 2017

机译：Calinescu-Karloff-Rabani松弛多路切割的改进的整体间隙
5. Fantastic Relaxations of the TSP and How to Bound Them: Relaxations of the Traveling Salesman Problem and Their Integrality Gaps [D] . Gutekunst, Samuel Christian. 2020

机译：TSP的奇妙放松以及如何绑定它们：放松旅行的推销员问题及其完整性差距
6. Learning Kernels for variants of Normalized Cuts: Convex Relaxations and Applications [O] . Lopamudra Mukherjee, Vikas Singh, Jiming Peng, -1

机译：学习内核的标准化切割的变体：凸松弛及应用
7. An Improved Integrality Gap for the Calinescu-Karloff-Rabani Relaxation for Multiway Cut [O] . Angelidakis, Haris, Makarychev, Yury, Manurangsi, Pasin 2016

机译：Calinescu-Karloff-Rabani松弛的改进完整性差距用于multiway Cut

An Improved Integrality Gap for the Calinescu-Karloff-Rabani Relaxation for Multiway Cut

摘要

著录项

相似文献

相关主题

期刊订阅