|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Faster Algorithms for Half-Integral T-Path Packingстатья
- Авторы: Babenko Maxim, Artamonov Stepan
- Сборник: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
- Том: 92
- Год издания: 2017
- Место издания: Leibniz International Proceedings in Informatics (LIPIcs)
- DOI: 10.4230/LIPIcs.ISAAC.2017.8
- Аннотация: Строится быстрый алгоритм для нахождения семейства непересекающихся путей между данными парами терминалов. Let G = (V, E) be an undirected graph, a subset of vertices T be a set of terminals. Then a natural combinatorial problem consists in finding the maximum number of vertex-disjoint paths connecting distinct terminals. For this problem, a clever construction suggested by Gallai reduces it to computing a maximum non-bipartite matching and thus gives an O(mn^1/2 log(n^2/m)/log(n))-time algorithm (hereinafter n := |V|, m := |E|). Now let us consider the fractional relaxation, i.e. allow T-path packings with arbitrary nonnegative real weights. It is known that there always exists a half-integral solution, that is, one only needs to assign weights 0, 1/2, 1 to maximize the total weight of T-paths. It is also known that an optimum half-integral packing can be found in strongly-polynomial time but the actual time bounds are far from being satisfactory. In this paper we present a novel algorithm that solves the half-integral problem within O(mn^1/2 log(n^2/m)/log(n)) time, thus matching the complexities of integral and half-integral versions. Пусть G = (V, E) - неориентированный граф, T ⊆ V некое подмножество вершин. Одна из стандартных задач комбинаторной оптимизации заключается в нахождении максимального набора вершинно-непересекающихся T-путей. Для этой задачи Галлаи предложил сведение к задаче нахождения максимального паросочетания, которую можно решить за время O(m\sqrt{n}\log(n^2/m)/\log(n) (n := |V |, m := |E|). Рассмотрим теперь случай вещественных неотрицательных весов на T-путях. Известно, что в оптимальном решении веса всегда можно выбрать из множества {0, 1/2, 1}. Также известно, что задача может быть решена за полиномиальное время, однако известные асимптотические оценки времени довольно большие. В данной статье приводится новый алгоритм, решающий эту задачу за время O(m\sqrt{n}\log(n^2/m)/\log(n), устанавливая одинаковые наилучшие асимптотические временные оценки для случаев целочисленных и вещественных весов.
- Добавил в систему: Верещагин Николай Константинович