Citeseer/On the Lasserre\Sum-of-Squares Hierarchy with Knapsack Covering Inequalities (2014) 10.1.1.764.6296 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
{{checked|}} | {{checked|}} | ||
| − | {{citeseerlink|citeseer/On the Lasserre\Sum-of-Squares Hierarchy with Knapsack Covering Inequalities (2014) 10.1.1.764.6296| | + | {{citeseerlink|citeseer/On the Lasserre\Sum-of-Squares Hierarchy with Knapsack Covering Inequalities (2014) 10.1.1.764.6296| |
| + | «Иерархия Лассерре/Сумма квадратов» — это систематическая процедура усиления релаксаций ЛП путем построения последовательности все более жестких формулировок. Для широкого круга оптимизационных задач этот подход позволяет получить выпуклые релаксации, используемые в лучших | ||
| + | доступных алгоритмах аппроксимации. | ||
| + | ИП емкостного покрытия — это целочисленная программа вида «min{cx : U x ≥ d, 0 ≤ x ≤ b, x ∈ Z+}», где все записи c, U и d неотрицательны. | ||
| − | + | Одна из трудностей аппроксимации задач с емкостным покрытием заключается в том, что отношение оптимального решения IP к оптимальному решению LP может достигать ||d||∞, даже если U состоит из одной строки (то есть задача «Min Knapsack»). | |
| + | |||
| + | В настоящее время самое сильное ослабление линейной программы получается путем добавления (экспоненциально большого числа) допустимых неравенств, введенных Вулси (''Wolsey''), что дает очень мощный способ решения этих проблем. | ||
| + | |||
| + | Для задачи «Min Knapsack» мы доказываем, что даже после непостоянного числа уровней «иерархия Лассерра/Сумма квадратов» не улучшает разрыв интегральности 2, подразумеваемый начальными (KC) неравенствами. | ||
| + | |||
| + | Более того, мы показываем, что разрыв интегральности релаксации остается M для особого случая ∑i xi ≥ 1/M при старте со стандартного | ||
| + | политопа Min Knapsack. | ||
| + | |||
| + | Мы отмечаем, что Min Knapsack допускает FPTAS, и наши результаты количественно определяют фундаментальную слабость иерархии Лассерра/суммы квадратов для этой базовой задачи. | ||
| + | }} | ||
{{enddiv}} | {{enddiv}} | ||
[[Категория:CiteSeerArticles]] | [[Категория:CiteSeerArticles]] | ||
Версия 15:29, 23 ноября 2021
«On the Lasserre\Sum-of-Squares Hierarchy with Knapsack Covering Inequalities (2014) 10.1.1.764.6296»скачать
«
«Иерархия Лассерре/Сумма квадратов» — это систематическая процедура усиления релаксаций ЛП путем построения последовательности все более жестких формулировок. Для широкого круга оптимизационных задач этот подход позволяет получить выпуклые релаксации, используемые в лучших доступных алгоритмах аппроксимации.
ИП емкостного покрытия — это целочисленная программа вида «min{cx : U x ≥ d, 0 ≤ x ≤ b, x ∈ Z+}», где все записи c, U и d неотрицательны.
Одна из трудностей аппроксимации задач с емкостным покрытием заключается в том, что отношение оптимального решения IP к оптимальному решению LP может достигать …»