Понимание ошибки аппроксимации и сложности запросов в маршрутизации WormHole

Таблица ссылок

Резюме и 1. Введение

1.1 Наш вклад

1.2 Настройка

1.3 Алгоритм

1. Связанные работы

2. Алгоритм

   3.1 Фаза структурной декомпозиции

   3.2 Фаза маршрутизации

   3.3 Варианты WormHole

3. Теоретический анализ

   4.1 Предварительные сведения

   4.2 Сублинейность внутреннего кольца

   4.3 Ошибка аппроксимации

   4.4 Сложность запросов

4. Экспериментальные результаты

   5.1 WormHole𝐸, WormHole𝐻 и BiBFS

   5.2 Сравнение с методами на основе индексов

   5.3 WormHole как примитив: WormHole𝑀

Ссылки

4.3 Ошибка аппроксимации

Теперь, когда у нас есть сублинейное внутреннее кольцо, содержащее ядро Чунг-Лу, мы должны показать, что маршрутизация путей через него влечет лишь небольшой штраф. Интуитивно понятно, что чем больше внутреннее кольцо, тем легче это удовлетворить: если внутреннее кольцо - это весь граф, утверждение выполняется тривиально. Поэтому задача заключается в том, чтобы показать, что мы можем достичь сильной гарантии в отношении точности даже с сублинейным внутренним кольцом. Мы доказываем, что WormHole влечет аддитивную ошибку не более 𝑂(loglog𝑛) для всех пар, что намного меньше диаметра Θ(log𝑛).

\

\ Вышеуказанный результат справедлив с высокой вероятностью даже в худшем случае. А именно, для всех пар (𝑠,𝑡) вершин в графе длина пути, возвращаемого WormHole, не более чем на 𝑂(loglog𝑛) превышает фактическое расстояние между 𝑠 и 𝑡. Это тривиально означает, что средняя аддитивная ошибка WormHole с высокой вероятностью ограничена той же величиной.

\

\

4.4 Сложность запросов

Вспомним модель запросов узлов в этой статье (см. §1.2): начиная с одного узла, нам разрешено итеративно делать запросы, где каждый запрос извлекает список соседей выбранного нами узла 𝑣. Нас интересует сложность запросов, т.е. количество запросов, необходимых для выполнения определенных операций.

\ \

\ \ Первый результат - это верхняя граница нашей производительности.

\ \

\ \ Набросок доказательства. Для данного запроса SP(𝑢, 𝑣) мы даем верхнюю границу сложности запросов BFS, который начинается с 𝑢, и аналогично для 𝑣; общая сложность запросов - это сумма этих двух величин.

\ \

\ \ \

\ \ \

\ \ \

\ \ \

\ \

:::info Авторы:

(1) Talya Eden, Университет Бар-Илан (talyaa01@gmail.com);

(2) Omri Ben-Eliezer, MIT (omrib@mit.edu);

(3) C. Seshadhri, UC Santa Cruz (sesh@ucsc.edu).

:::

:::info Эта статья доступна на arxiv под лицензией CC BY 4.0.

:::

\