Страница публикации

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

Авторы: Груздева Т.В., Стрекаловский А.С.

Журнал:

Том:

Номер:

Год: 2014

Отчётный год: 2014

Издательство: Наука

Местоположение издательства: Новосибирск

URL:

Проекты:

DOI:

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

Индексируется WOS: Нет

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Нет

Индексируется ВАК: Нет

Индексируется CORE: Нет

Публикация в печати: 0