Citeseer/On the Lasserre\Sum-of-Squares Hierarchy with Knapsack Covering Inequalities (2014) 10.1.1.764.6296

Ссылки сюда (1) →

«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 может достигать …»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.