Космический аппроксимация

В своей статье « Приблизительные расстояния» оракулы Торупа и Цвика показали, что для любого взвешенного неориентированного графа можно построить структуру данных размера которая может возвращать -приближенный расстояние между любой парой вершин в графе. $O(k n^{1+1/k})$ $(2k-1)$

На фундаментальном уровне эта конструкция обеспечивает компромисс между пространством и аппроксимацией - можно снизить требования к пространству за счет более низкого «качества» решения.

Какие другие графические проблемы демонстрируют такой компромисс между пространством и приближением?

Меня интересуют как статические, так и динамические, взвешенные и невзвешенные, ненаправленные и ориентированные графы.

Благодарю.

ds.algorithms graph-theory approximation-algorithms space-complexity Rachit
источник

Компромисс обычно означает нижнюю границу: если вы делаете одну вещь меньше, то другая должна быть больше. Вы хотите получить результат с верхней границей (как в вашем примере) или результат с нижней границей?

Ёсио Окамото

@YoshioOkamoto - Верхняя граница может «достичь» компромисса - верхняя граница может не означать, что компромисс является существенным (это вопрос нижней границы), но она может его достичь. Это правильно? Независимо от этого меня интересуют как нижние, так и верхние границы.

Rachit

Ответы:

-2

Похоже, что это исследование более активно в прикладном смысле, чем упомянутое вами теоретическое (т.е. оракулы и т. д.) с алгоритмами «потоковой передачи данных», которые пытаются работать с очень большими данными через «скользящие окна», с учетом многих алгоритмов на графиках, но действительно относительно новый / недавний, соответствующий направлениям исследований «больших данных» .

Алгоритмы компромисса в потоковых моделях , Andrea Ribichini, p7:

Мы разработали несколько алгоритмов для фундаментальных графовых задач в модели W-Stream, включая связанные компоненты, минимальное связующее дерево, двусвязные компоненты и кратчайшие пути из одного источника. Насколько нам известно, наши алгоритмы являются первыми, которые позволяют эффективно компенсировать пространство / пропускать такие проблемы при настройке потоковой передачи данных.

Эта ссылка включает в себя другие ссылки / опросы, которые могут быть полезны.

Несмотря на серьезные ограничения, налагаемые [классической потоковой] моделью, был достигнут значительный успех для нескольких задач построения эскизов данных и статистики, для которых было доказано, что постоянное количество проходов и полилогарифмическая рабочая память достаточно для нахождения приближенных решений (см. [4, 16, 17] и обширные библиографии в [7, 29]).

также:

Замена пространства для пропусков в задачах потокового графа Камил Деметреску, Ирэн Финокки, Андреа Рибикини

ВЗН
источник