|
Сибирский журнал вычислительной математики, 2011, том 14, номер 4, страницы 409–423
(Mi sjvm451)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Кусочно-выпуклые формулировки бинарных и перестановочных задач
Д. Фортинa, И. Цевеендоржb a INRIA, Domaine de Voluceau, Le Chesnay Cedex, France
b Laboratoire PRiSM, UMR 8144, Université de Versailles, Versailles Cedex, France
Аннотация:
Хорошо известно, что максимизацию любой разности выпуклых функций можно трансформировать в выпуклую максимизацию; здесь наша цель – получить вместо этого кусочно-выпуклую максимизацию задачи. Несмотря на то, что это может показаться более трудным, иногда размерность может быть уменьшена на единицу и локальный поиск может быть улучшен путем использования экстремальных точек замыкания выпуклой оболочки лучших точек. Мы показываем, что это всегда имеет место как для бинарных, так и для перестановочных задач, и даем, в качестве примера, кусочно-выпуклые формулировки задачи о максимальной клике и квадратичной задачи о назначениях.
Ключевые слова:
кусочно-выпуклый, максимальная клика, QAP, DC.
Статья поступила: 05.11.2010 Переработанный вариант: 04.03.2011
Образец цитирования:
Д. Фортин, И. Цевеендорж, “Кусочно-выпуклые формулировки бинарных и перестановочных задач”, Сиб. журн. вычисл. матем., 14:4 (2011), 409–423; Num. Anal. Appl., 4:4 (2011), 333–344
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/sjvm451 https://www.mathnet.ru/rus/sjvm/v14/i4/p409
|
Статистика просмотров: |
Страница аннотации: | 186 | PDF полного текста: | 58 | Список литературы: | 32 | Первая страница: | 2 |
|