Минимальные k-связные геометрические сети: различия между версиями

Перейти к навигации Перейти к поиску

Минимальные k-связные геометрические сети (посмотреть исходный код)

Версия от 16:16, 14 сентября 2016

1237 байт добавлено ,  14 сентября 2016
нет описания правки
Нет описания правки
Строка 54: Строка 54:
Схема аппроксимации с полиномиальным временем исполнения (PTAS) представляет собой семейство алгоритмов fA" g, такое, что для каждого фиксированного " > 0 алгоритм A" исполняется за время, полиномиальное относительно размера входного графа, и дает (1 + ")-аппроксимацию.
Схема аппроксимации с полиномиальным временем исполнения (PTAS) представляет собой семейство алгоритмов fA" g, такое, что для каждого фиксированного " > 0 алгоритм A" исполняется за время, полиномиальное относительно размера входного графа, и дает (1 + ")-аппроксимацию.


== Родственные работы ==
Исчерпывающий обзор результатов решения задач о нахождении k-вершинно-связных или k-реберно-связных остовных подграфов с минимальной стоимостью, задач о неоднородной связности, задач о пополнении связности и геометрических задач см. [1, 3, 11, 15].


== Родственные работы ==
For a very extensive presentation of results concerning problems of finding minimum-cost k-vertex- and k-edge-connected spanning subgraphs, non-uniform connectivity, connectivity augmentation problems, and geometric problems, see [1,3,11,15].


Despite the practical relevance of the multi-connectivity problems for geometrical networks and the vast amount of practical heuristic results reported (see, e.g., [12,13,17,18]), very little theoretical research had been done towards developing efficient approximation algorithms for these problems until a few years ago. This contrasts with the very rich and successful theoretical investigations of the corresponding problems in general metric spaces and for general weighted graphs. And so, until 1998, even for the simplest and most fundamental multi-connectivity problem, that of finding a minimum-cost 2-vertex connected network spanning a given set of points in the Euclidean plane, obtaining approximations achieving better than a | ratio had been elusive (the ratio
Несмотря на высокую практическую значимость задач о многосвязности в геометрических сетях и большое количество опубликованных практических эвристических результатов (см., например, [12, 13, 17, 18]), до недавнего времени совсем немного теоретических исследований было посвящено разработке эффективных алгоритмов аппроксимации этих задач. Эта ситуация резко контрастирует с обширным списком успешных теоретических исследований соответствующих задач в общеметрических пространствах и для взвешенных графов общего вида. Таким образом, до 1998 года даже для самой простой и наиболее фундаментальной задачи о многосвязности, а именно – задачи о нахождении 2-вершинно-связной сети минимальной стоимости, охватывающей заданный набор точек на евклидовой плоскости, не удавалось получить аппроксимации с лучшим коэффициентом, чем | (коэффициент | представляет собой наилучший коэффициент аппроксимации с полиномиальным временем выполнения, известный для сетей общего вида, веса которых удовлетворяют неравенству треугольника [8]. Другие результаты можно найти в [4, 15]).
| is the best polynomial-time approximation ratio known for general networks whose weights satisfy the triangle inequality [8]; for other results, see e. g., [4,15]).


Key Results
== Основные результаты ==
The first result is an extension of the well-known NP-hardness result of minimum-cost 2-connectivity in general graphs (see, e. g., [    ]) to geometric networks.
The first result is an extension of the well-known NP-hardness result of minimum-cost 2-connectivity in general graphs (see, e. g., [    ]) to geometric networks.


Irina
4551

правка

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/11836

Навигация