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

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

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

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

790 байт добавлено ,  15 сентября 2016
→‎Основные результаты
Нет описания правки
Строка 61: Строка 61:


== Основные результаты ==
== Основные результаты ==
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.
Первым результатом является расширение хорошо известного понятия о NP-полноте задачи 2-связной сети минимальной стоимости в графах общего вида (см., например, [    ]) на геометрические сети.


Theorem 1 The problem of finding a minimum-cost 2-vertex/edge connected geometric network spanning a set of n points in the plane is NP T-hard.


Next result shows that if one considers the minimum-cost multi-connectivity problems in an enough high dimension, the problems become APX-hard.
Теорема 1. Задача нахождения 2-вершинно/реберно-связной геометрической сети минимальной стоимости, охватывающей набор из n точек на плоскости, является NPT-полной.


Theorem 2 ([6]) There exists a constant £ > 0 such that it is NP-hard to approximate within 1 + % the minimum-cost 2-connected geometric network spanning a set of n points in Rdlog2ne.
Следующий результат показывает, что если рассматривать задачи о многосвязности с нахождением объектов минимальной стоимости для достаточно большой размерности, эти задачи становятся APX-полными.
 
 
Теорема 2 ([6]). Существует константа £ > 0, такая, что задача аппроксимации 2-связной геометрической сети минимальной стоимости, охватывающей набор из n точек в Rdlog2ne, с коэффициентом 1 + % является NPT-полной.
 
Этот результат также можно расширить на любую lp-норму.


This result extends also to any lp norm.


Theorem 3 ([6])  For and integer d > log n and for any fixed p > 1 there exists a constant f > 0 such that it is NP-hard to approximate within 1 + f the minimum-cost 2-connected network spanning a set of n points in the lp metric in Rd.
Theorem 3 ([6])  For and integer d > log n and for any fixed p > 1 there exists a constant f > 0 such that it is NP-hard to approximate within 1 + f the minimum-cost 2-connected network spanning a set of n points in the lp metric in Rd.
Irina
4551

правка

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

Навигация