Аноним

Декомпозиция на значительно удаленные пары: различия между версиями

Материал из WEGA
м
Строка 84: Строка 84:


== Открытые вопросы ==
== Открытые вопросы ==
Важнейшей нерешенной проблемой является разрыв между <math>\Omega(n) \;</math> и O(n log n) в количестве необходимых пар на плоскости. Кроме того, временная граница <math>(1 + \varepsilon) \;</math>-аппроксимации до сих пор близка к <math>\tilde{O} (n \sqrt{n})</math> из-за отсутствия эффективных способов вычисления <math>(1 + \varepsilon) \;</math>-приближенных расстояний по кратчайшим путям между O(n) парами точек. Любое улучшение алгоритма решения этой задачи немедленно приведет к улучшению всех алгоритмов <math>(1 + \varepsilon) \;</math>-аппроксимации, упоминавшихся выше.
Важнейшей нерешенной проблемой является разрыв между <math>\Omega(n) \;</math> и <math>O(n \; log \; n)</math> в количестве необходимых пар на плоскости. Кроме того, временная граница <math>(1 + \varepsilon) \;</math>-аппроксимации до сих пор близка к <math>\tilde{O} (n \sqrt{n})</math> из-за отсутствия эффективных способов вычисления <math>(1 + \varepsilon) \;</math>-приближенных расстояний по кратчайшим путям между O(n) парами точек. Любое улучшение алгоритма решения этой задачи немедленно приведет к улучшению всех алгоритмов <math>(1 + \varepsilon) \;</math>-аппроксимации, упоминавшихся выше.


== См. также ==
== См. также ==
4551

правка