Abstract: Задачи кластеризации являются важной частью анализа данных. В них требуется разбить заданное множество объектов на несколько подмножеств (кластеров) на основе сходства объектов друг с другом. Задача кластеризации вершин графа является формализацией задачи кластеризации. Сходство объектов задаётся с помощью рёбер некоторого графа, вершины которого взаимно однозначно соответствуют объектам. Существует множество вариантов задачи: с ограничением на число и размер кластеров, взвешенные и ориентированные постановки; все известные варианты задачи являются NP-трудными. Данная работа посвящена одному из подходов к решению задачи - построению моделей целочисленного линейного программирования. Приведён обзор известных и предложены новые подходы к построению таких моделей. Новые модели могут использоваться как для нахождения точных решений, так и для построения приближённых алгоритмов. Проведён вычислительный эксперимент, направленный на оценку времени, необходимого алгоритмам, опирающимся на различные модели, для нахождения точного решения. Показано, что один из алгоритмов, опирающихся на новые модели, быстрее других находит решение для задачи с ограниченным числом кластеров.

Cite: Моршинин А.В.
О целочисленном линейном программировании для задач кластеризации вершин графа
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2025. №70. С.45-64. DOI: 10.17223/20710410/70/3 РИНЦ

Dates:

Published print:	Jan 9, 2026
Published online:	Jan 9, 2026

Identifiers:

Elibrary:

88744534

Citing: Пока нет цитирований

Altmetrics: