|
Задача минимального неравномерного разбиения графа на части c несвязанными весами
К. С. Макарычевa, Ю. С. Макарычевb a Northwestern University, Evanston, IL, USA
b Toyota Technological Institute at Chicago, Chicago, IL, USA
Аннотация:
Приводится бикритериальный аппроксимационный алгоритм для задачи минимального разбиения графа на (неравные) части, недавно предложенной Р. Краутгеймером, Дж. Наором, Р. Шварцем и К. Талваром. В этой задаче даны граф $G=(V, E)$ и $k$ чисел $\rho_1, \dots , \rho_k$. Цель состоит в нахождении разбиения множества вершин $V$ на $k$ непересекающихся множеств (кластеров) $P_1, \dots, P_k$, минимизирующего число разрезанных ребер и удовлетворяющего условию $|P_i| \leq (5+\varepsilon) \rho_i |V|$ для всех $i$. Построенный бикритериальный алгоритм дает аппроксимацию $O(\sqrt{\log |V | \log k})$ для произвольных графов и константную аппроксимацию для графов с исключенным фиксированным минором.
Приближенное решение удовлетворяет ослабленным ограничениям на размеры частей: $|P_i| \leq (5+ \varepsilon)\rho_i |V|$. Данный алгоритм улучшает алгоритм Краутгеймера, Наора, Шварца и Талвара, у которого коэффициент аппроксимации равен $O(\log |V|)$.
Полученные результаты обобщаются на случай “несвязанных весов” и на случай "несвязанных $d$-мерных весов".
Предварительный вариант настоящей работы был представлен на 41-м международном коллоквиуме по автоматам, языкам и программированию (ICALP 2014).
Библиография: 7 названий.
Ключевые слова:
задача минимального разбиения графа на неравные части, задача минимального разбиения графа на неравные части с несвязными весами, приближение на деревьях, аппроксимационный алгоритм, полуопределенное программирование.
Поступила в редакцию: 31.12.2016 и 17.07.2017
Образец цитирования:
К. С. Макарычев, Ю. С. Макарычев, “Задача минимального неравномерного разбиения графа на части c несвязанными весами”, Матем. сб., 208:12 (2017), 124–143; K. S. Makarychev, Yu. S. Makarychev, “Minimum nonuniform graph partitioning with unrelated weights”, Sb. Math., 208:12 (2017), 1835–1853
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/sm8903https://doi.org/10.4213/sm8903 https://www.mathnet.ru/rus/sm/v208/i12/p124
|
|