Издательство СО РАН

Издательство СО РАН

Адрес Издательства СО РАН: Россия, 630090, а/я 187
Новосибирск, Морской пр., 2

soran2.gif

Baner_Nauka_Sibiri.jpg


Яндекс.Метрика

Название:
Раздел:
 
Авторы:
Год выпуска:  до 
Ключевые слова:
   

Задачи о клике и невыпуклая оптимизация

Задачи о клике и невыпуклая оптимизация

Груздева Т.В., Стрекаловский А.С.
Новосибирск: Изд-во "Наука", 2014 г., 202 с., Тираж 300, ISBN 978-5-02-019183-9

Для поиска в простом неориентированном графе полного подграфа (клики) с максимально возможным количеством вершин или полного подграфа максимально возможного веса (максимальной взвешенной клики) предлагается подход, основанный на редукции к непрерывным невыпуклым задачам оптимизации. В полученных непрерывных задачах целевую функцию или ограничения задают функции, представимые в виде разности двух выпуклых (d.c. функции).
Для их решения с учетом свойств задач о клике разработаны новые алгоритмы, базирующиеся на теории глобального поиска в задачах d.c. программирования. Предложены новые методы локального поиска и новый способ построения оценок на вес и мощность клик.
Проведен обширный вычислительный эксперимент на графах из библиотеки DIMACS, демонстрирующий эффективность предлагаемого подхода и его сравнение с некоторыми другими непрерывными методами решения задач о клике.
В приложении приведена теория и методы решения задач d.c. программирования: d.c. максимизация и задач с d.c. ограничением.
Для специалистов в области дискретной и непрерывной оптимизации, а также аспирантов и студентов соответствующих специальностей. На основе отдельных глав монографии могут быть прочитаны курсы лекций для студентов математических факультетов университетов.
Табл. 14. Ил.1. Библиогр.: 163 назв.

710 руб В корзину