4551
правка
Минимальные k-связные геометрические сети: различия между версиями
Материал из WEGA
Минимальные k-связные геометрические сети (посмотреть исходный код)
Версия от 23:02, 17 сентября 2016
, 17 сентября 2016→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 120: | Строка 120: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Вышеприведенные результаты позволяют создавать эффективные алгоритмы только для малых значений требования связности k; время выполнения является полиномиальным только для значения k, не превышающего (log log n) для определенной положительной константы c < 1. Любопытно было бы узнать, можно ли получить алгоритм схемы аппроксимации с полиномиальным временем выполнения для больших значений k. | Вышеприведенные результаты позволяют создавать эффективные алгоритмы только для малых значений требования связности k; время выполнения является полиномиальным только для значения k, не превышающего <math>(log \; log \; n)^c</math> для определенной положительной константы c < 1. Любопытно было бы узнать, можно ли получить алгоритм схемы аппроксимации с полиномиальным временем выполнения для больших значений k. | ||
