Метод оптимальной группировки векторных объектов относительно центров
Ключевые слова:
алгоритм, группировка, целочисленное программирование, поток в сети, матроидАннотация
Рассматривается задача группировки векторных объектов относительно возможных центров с учетом ограничений на состав групп. Предлагается способ представления специфических векторных ограничений в виде ограничений эквивалентной задачи целочисленного программирования и полиномиальные алгоритмы для некоторых частных случаев.Литература
Bertsekas D. Linear Network Optimization: Algorithms and Codes. The MIT Press, 1991
Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2000
Edmonds J. Matroids and the Greedy Algorithm. Mathematical Programming, volume 1, p.125–136. 1971
Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2000
Edmonds J. Matroids and the Greedy Algorithm. Mathematical Programming, volume 1, p.125–136. 1971
A method for optimal grouping of vector objects around centers
Abstract
The paper addresses the problem of grouping vector objects around potential centers with respect to restrictions imposed on the group structure. A method for transforming vector restictions into the restictions of equivalent integer programming problem is proposed. Polynomial algorithms for some special cases are suggested.Опубликован
2012-03-01
Как цитировать
Мустафин, Н. Г., Пономарев, А. В., & Савосин, С. В. (2012). Метод оптимальной группировки векторных объектов относительно центров. Труды СПИИРАН, 1(20), 216-230. https://doi.org/10.15622/sp.20.12
Раздел
Статьи
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
