Citeseer/On the Lasserre\Sum-of-Squares Hierarchy with Knapsack Covering Inequalities (2014) 10.1.1.764.6296
Материал из DISCOPAL
Версия от 15:29, 23 ноября 2021; StasFomin (обсуждение | вклад)
«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 может достигать …»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.