Двойственные оценки для задачи о максимальном К-клабе

Abstract

Рассмотрены возможности формирования квадратичных постановок задачи о максимальном k-клабе и, соответственно, нахождения верхних двойственных оценок, получаемых с помощью техники Н.З. Шора. На примере задачи о максимальном 2-клабе показано, что неоднозначность построения соответствующих квадратичных задач (в том числе с учетом добавления функционально избыточных ограничений) предоставляет значительные возможности для уточнения двойственных оценок.

Розглянуті можливості формування квадратичних постановок задачі про максимальний k-клаб і, відповідно, знаходження верхніх двоїстих оцінок, які можна отримати за допомогою техніки Н.З. Шора. На прикладі задачі про максимальний 2-клаб показано, що неоднозначність побудови відповідних квадратичних задач (у тому числі з урахуванням додавання функціонально надлишкових обмежень) надає значні можливості для уточнення двоїстих оцінок.

The opportunities of constraining quadratic formulations of k-club problem and, accordingly, finding of upper dual bounds received by using Shor's engineering are considered. On an example of 2­club problem it's shown, that the ambiguity of construction of the appropriate quadratic problems (including in view of addition of functional superfluous restrictions) gives significant opportunities to improve of dual bounds.