Вычисление расстояний с аппроксимацией менее 2 в общих графиках?

Учитывая взвешенный неориентированный граф с $m = o(n^2)$ ребрами, я хотел бы вычислить расстояния приближения меньше 2 между любой данной парой вершин. Конечно, я хотел бы использовать субквадратичное пространство и время сублинейного запроса.

Мне известен результат Цвика, который использует умножение матриц, но мне любопытно, известны ли какие-либо комбинаторные алгоритмы для этой проблемы?

ds.algorithms graph-algorithms Сиддхартха
источник

Привет @Siddhartha, я извиняюсь, если это глупый вопрос: результат Цвика, кажется, использует квадратичное пространство, это правильно?

Сянь-Чжи Чанг 之之

Кроме того, допускается ли аддитивная ошибка?

Сянь-Чи Чанг 之之

@ Hsien-ChihChang 張顯之 - меня интересовали результаты только по мультипликативному приближению. Случай аддитивного приближения может быть интересен сам по себе - проще для плотных графов, я полагаю. Можно использовать гаечный ключ и получить аддитивное приближение для достаточно плотных графиков. Для разреженных графиков, насколько я знаю, гаечные ключи не помогли бы.

Сиддхартха

Разве следующий аргумент не работает? Рассмотрим любой граф

вершинами и

ребрами. Рассмотрим все веса ребер равными

. любой дистанционный оракул, который может иметь строго лучшее приближение, чем

, может использоваться для определения для каждого возможного ребра, независимо от того, находится он на графике или нет. Но это, конечно , означает , что такое расстояние оракул должен использовать

бит. Нет? (Аргумент немного волнистый, но должен быть правильным.) (Формально количество битов равно , где . Это .

G

$G$

n

$n$

m

$m$

1

$1$

2

$2$

Ω (m)

$\Omega(m)$

\log_{2} (\binom{N}{m})

$\log_2 \binom{N}{m}$

N = (\binom{n}{2})

$N=\binom{n}{2}$

\geq m \log_{2} (N / m)

$\geq m \log_2 (N/m)$

Сариэль Хар-Пелед

Спасибо Сариэль - может быть возможно получить нижнюю границу но я в порядке с этим. Все, что я хотел бы иметь, это субквадратичное пространство и сублинейное время запроса. Для графов с ребрами нижняя граница ничего не говорит о проблеме - верно?

Ω (m)

$\Omega(m)$

m = o (n^{2})

$m = o(n^2)$

Ω (m)

$\Omega(m)$

Сиддхартха

Ответы:

Насколько я знаю, не существует опубликованных результатов по вычислению расстояний приближения менее 2 в субквадратичном пространстве и времени сублинейного запроса. Для быстрого получения приблизительных расстояний вы можете обратиться к результатам и ссылкам в «Более быстрых алгоритмах для приблизительных кратчайших путей для всех пар» Басваны и Кавиты (в журнальной версии их статьи FOCS есть хороший обзор соответствующей работы); ни один из них не достигает субквадратичного пространства.

Для компактного извлечения приблизительных расстояний вы можете посмотреть результаты и ссылки в двух вышеупомянутых статьях. [В дополнение к ответу Габора, предостережение: будьте осторожны с понятием разреженности в вышеприведенных работах - для приближения график называется разреженным, если , так как вы наверное, уже знаю]. $2$ $m = o(n^2)$

Как Сариэль указал в одном из комментариев выше, естественная нижняя граница пространства для вычисления расстояний приближения меньше является , то есть линейной по размеру графика. Если время запроса не ограничено, эта нижняя граница не может быть улучшена (тривиально, можно использовать алгоритм кратчайшего пути, просто сохраняя график). Для постоянного времени запроса я знаю две нижние границы. Во-первых, у Патраску и Роддити были некоторые условные нижние оценки в их статье FOCS 2010, которые применяются для аппроксимации менее . Во-вторых, Sommer et. и др. имел некоторые нижние оценки для очень разреженных графов. Я не знаю ни о каких других (нетривиальных) нижних границах. $2$ $\Omega(m)$ $2$

В терминах верхних оценок результаты вышеприведенных работ, по-видимому, не обобщаются до приближения менее . Недавно мы достигли некоторого прогресса в решении этой проблемы. Бумага должна появиться на ArXiv в ближайшее время, но, если хотите, пришлите мне электронное письмо, и я с удовольствием поделюсь этой статьей. $2$

Надеюсь это поможет.

~ Рачит Агарвал

Rachit
источник

Вас может заинтересовать документ INFOCOM от Rachit Agarwal за 2011 год:

Rachit Agarwal, P. Brighten Godfrey, Sariel Har-Peled Приблизительные дистанционные запросы и компактная маршрутизация в разреженных графах, IEEE INFOCOM 2011

Из аннотации:

[Для] графа со средней степенью , частные случаи наших структур данных извлекают 2 протяженных пути с пробелом [...] за счет время запроса. $\Theta(\log n)$ $O(n^{3/2})$ $O(\sqrt{n})$

Обратите внимание, что их оракул расстояния только для разреженных графов, но логарифмическая оценка степени кажется правдоподобной. Дополнительный бонус, алгоритм также работает для взвешенных графиков.

Габор Ретвари
источник

Вы также можете взглянуть на

Патрашку, Родитты, Оракулы на расстоянии за Торупом - Цвик Бонд, FOCS 2010

У них есть дистанционный оракул размером с натяжкой 2. Он поддерживает запросы в постоянное время. $O(n^{5/3})$

zotachidil
источник

Благодаря! Бумага из Агравала и Михая, кажется, ничего не говорит о приближении «меньше, чем» 2, если я что-то пропустил.

Сиддхартха

Это не так, но это может дать вам представление о том, как получить компромисс, чтобы улучшить натяжение.

зотачидил