О целочисленном линейном программировании для задач кластеризации вершин графа

doi:10.17223/20710410/70/3

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
О целочисленном линейном программировании для задач кластеризации вершин графа	5 MB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/70/3

#кластерные графы

#целочисленное линейное программирование

#NР-трудная задача

Title: О целочисленном линейном программировании для задач кластеризации вершин графа
Title: On an integer linear programming for correlation clustering
Creator: Моршинин, Александр Владимирович
Date: 2025
DOI: 10.17223/20710410/70/3
Description: Задачи кластеризации являются важной частью анализа, данных. В них требуется разбить заданное множество объектов на несколько подмножеств (кластеров) на основе сходства объектов друг с другом. Задача кластеризации вершин графа является формализацией задачи кластеризации. Сходство объектов задается с помощью ребер некоторого графа, вершины которого взаимно однозначно соответствуют объектам. Существует множество вариантов задачи: с ограничением на число и размер кластеров, взвешенные и ориентированные постановки; все известные варианты задачи являются NР-трудными. Данная работа посвящена одному из подходов к решению задачи - построению моделей целочисленного линейного программирования. Приведен обзор известных и предложены новые подходы к построению таких моделей. Новые модели могут использоваться как для нахождения точных решений, так и для построения приближенных алгоритмов. Проведен вычислительный эксперимент, направленный на оценку времени, необходимого алгоритмам, опирающимся на различные модели, для нахождения точного решения. Показано, что один из алгоритмов, опирающихся на новые модели, быстрее других находит решение для задачи с ограниченным числом кластеров.

Relationships: Show Relationship Browser for this Object
collection(s): Журналы ТГУ
Identifier: смотреть в электронном каталоге НБ ТГУ
Relation: Прикладная дискретная математика
Type: статьи в журналах
Source: Прикладная дискретная математика. 2025. № 70. С. 45-64
Language: rus

Created: 09-12-2025

2 Visitors

2 Hits

0 Downloads

Журналы ТГУ О целочисленном линейном программировании для задач кластеризации вершин графа