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

Несмотря на высокую практическую значимость задач о многосвязности в геометрических сетях и большое количество опубликованных практических эвристических результатов (см., например, [12, 13, 17, 18]), до недавнего времени совсем небольшое число теоретических исследований было посвящено разработке эффективных алгоритмов аппроксимации этих задач. Эта ситуация резко контрастирует с обширным списком успешных теоретических исследований соответствующих задач на общеметрических пространствах и для взвешенных графов общего вида. Таким образом, до 1998 года даже для самой простой и наиболее фундаментальной задачи о многосвязности, а именно – задачи о нахождении 2-вершинно-связной сети минимальной стоимости, охватывающей заданный набор точек на евклидовой плоскости, не удавалось получить аппроксимации с лучшим коэффициентом, чем | (коэффициент | представляет собой наилучший известный коэффициент аппроксимации с полиномиальным временем выполнения для сетей общего вида, веса в которых удовлетворяют неравенству треугольника [8]. Другие результаты можно найти в [4, 15]).