УДК 519.85
П.I. СТЕЦЮК,
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
stetsyukp@gmail.com
О.М. ХОМ’ЯК,
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
khomiak.olha@gmail.com
Є.А. БЛОХІН,
Техаський університет A&M, Колледж-Стейшен, Сполучені Штати Америки,
blokhin23@tamu.edu
А.А. СУПРУН,
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
anton_s2007@ukr.net
ОПТИМІЗАЦІЙНІ ЗАДАЧІ ДЛЯ МАКСИМАЛЬНОГО k-ПЛЕКСА
Анотація. Побудовано квадратичну оптимізаційну задачу для знаходження
максимального k-плекса у неорієнтованому графі. Наведено дві сім’ї функціонально-надлишкових квадратичних обмежень,
які отримано за допомогою обмежень Булевої задачі для максимального k-плекса.
Досліджено вплив функціонально-надлишкових обмежень на покращення точності
Лагранжевих двоїстих оцінок для цільової функції квадратичної задачі.
Розроблено алгоритм пошуку всіх максимальних k-плексів та наведено результати тестових
експериментів для його реалізації за допомогою програмного пакета GLPK (GNU Linear Programming Kit).
Ключові слова: максимальний k-плекс, максимальна кліка, квадратична оптимізаційна задача,
Булева задача лінійного програмування, функціонально-надлишкове обмеження, Лагранжева двоїста оцінка.
ПОВНИЙ ТЕКСТ
СПИСОК ЛІТЕРАТУРИ
- Seidman S.B., Foster B.L. A graph theoretic generalization of the clique concept. J. of Math. Sociology. 1978. Vol. 6. P. 139–154.
- Balansundaram B., Butenko S., Hicks I.V. Clique relaxations in social network analysis: The maximum k-plex problem. Operations Research. 2011. Vol. 59, N 1. P. 133–142.
- Guo J., Komusiewicz C., Niedermeier R., Uhlmann J. A more relaxed model for graph-based data clustering: s-plex cluster editing. SIAM J. Discrete Math. 2010. Vol. 24, N 4. P. 1662–1683.
- McClosky B., Hicks I.V. Combinatorial algorithms for the maximum k-plex problem. J. of Combinatorial Optimization. 2012. Vol. 23, N 1. P. 29–49.
- Pattillo J., Veremyev A., Butenko S., Boginski V. On the maximum quasi-clique problem. Discrete Applied Mathematics. 2013. Vol. 161, N 1–2. P. 244–257.
- Стецюк П.І., Бардадим Т.О., Ляшко В.І. Квадратична задача для максималь k-плекса в неорієнтованому графі. Журнал обчислювальної та прикладної математики. 2017. № 1 (124). C. 80–87.
- Стецюк П.І., Ляшко В.І., Бардадим Т.О. Властивості квадратичної задачі про максимальний -плекс у неорієнтованому графі. Наукові записки НаУКМА. Комп’ютерні науки. 2017. Т. 198, № 1(124). C. 80–87.
- Стецюк П.І., Хом’як О.М. Застосування пакету GLPK для знаходження всіх розв’язків задачі про -плекс. Матеріали XXIІІ Міжнародного науково-практичного семінару імені А.Я. Петренюка «Комбінаторні конфігурації та їхні застосування», присвяченого 70-річчю Льотної академії Національного авіаційного університету (13–15 травня 2021, Запоріжжя–Кропивницький, Україна). Запоріжжя–Кропивницький, 2021. Кропивницький: ПП «Ексклюзив-Систем», 2021. С. 174–179.
- Shor N.Z. Nondifferentiable optimization and polynomial problems. London; Boston; Dordrecht: Kluwer Academic Publishers, 1998. 394 p.
- Стецюк П.И. Двойственные оценки в квадратичных экстремальных задачах. Кишинэу: Эврика, 2018. 504 с.
- Shor N.Z., Stetsyuk P.I. Dual solution of quadratic-type problems by -algorithm (subroutine DSQTPr). Abstracts of the Second International Workshop “Recent Advances in Non-Differentiable Optimization” (1–4 October, 2001, Kyiv, Ukraine). Kyiv, 2001. P. 36.
- Eaton J.W., Bateman D., Hauberg S. GNU Octave Manual Version 3. Network Theory Ltd, 2008. 568 p.
- Стецюк П.И. О функционально избыточных ограничениях для булевых оптимизационных задач квадратичного типа. Кибернетика и системный анализ. 2005. Т. 41, № 6. C. 168–171.
- Стецюк П.И. Новые модели квадратичного типа для задачи о максимальном взвешенном разрезе графа. Кибернетика и системный анализ. 2006. Т. 42, № 1. C. 63––75.
