Archive for Сентябрь 2010

Мультипотоки и разреженные разрезы

Сентябрь 3, 2010

Хорошо известна теорема Форда-Фалкерсона: максимальный st поток равен минимальному st разрезу. Мы рассмотрим некоторый важный аналог этой теоремы для мультипотоков.

Более точно, будем рассматривать такую задачу. Задан ненаправленный граф G = (V, E) с неотрицательными пропускными способностями c_e на ребрах, в нем выделены k пар терминалов (s_i, t_i). Для каждой пары известно требование \mathrm{dem}(i). Мы хотим найти максимальное число f такое, что можно одновременно направить f \cdot \mathrm{dem}(i) единиц потока из s_i в t_i одновременно для всех i, соблюдая все пропускные способности. Обозначим этот минимум f^*. Ясно, что найти f^* очень просто, решив соответствующую линейную программу.

Можно рассмотреть в некотором смысле двойственную задачу. Как можно оценить f^* сверху? Рассмотрим какое-нибудь множество вершин S \subseteq V. Ясно, что f^* \leq c(\delta(S)) / \mathrm{dem}(S), где \delta(S) — множество ребер, ровно один конец которых лежит в S, а \mathrm{dem}(S) — сумма требований тех пар терминалов, которые лежат по разные стороны. Обозначим минимум этого отношения по всем S \alpha^*. Мы только что доказали, что f^* \leq \alpha^*.

Хотелось бы доказать обобщение теоремы Форда-Фалкерсона вида ‘f^* = \alpha^*‘. Однако, это, увы, неверно. Но, оказывается, можно доказать, что \alpha^* \leq f^* \cdot O(\log n). Далее мы изложим план доказательства, который кажется удивительным и загадочным.

Как мы уже упоминали, f^* можно найти за полиномиальное время, решив линейную программу. Оказывается, воспользовавшись теоремой двойственности для линейных программ, можно получить такое соотношение:

f^* = \min_d \left( \sum_{e = \{u, v\} \in E} c_e d(u, v)\right) / \left( \sum_{i = 1}^k \mathrm{dem}(i) d(s_i, t_i) \right),

где минимум берется по всем метрикам d на множестве вершин V.

Теперь мы рассмотрим вспомогательную задачу, так называемую упаковку разрезов. Рассмотрим метрику d на конечном множестве V. Каждому подмножеству S \subseteq V мы хотим сопоставить неотрицательное число y_S так, чтобы для каждой пары вершин (u, v) выполнялось ограничение \sum_{S: |\{u, v\} \cap S| = 1} y_S \leq d(u, v). Назовем упаковку разрезов y \beta-упаковкой, если, дополнительно потребовать, чтобы для каждой пары (u, v) выполнялось обратное неравенство: \sum_{S: |\{u, v\} \cap S| = 1} y_S \geq d(u, v) / \beta.

Оказывается, что если для метрики, полученной в результате решения двойственной программы, существует \beta-упаковка, то тогда \alpha^* \leq f^* \cdot \beta (это показать совсем нетрудно). Таким образом, нам достаточно доказать, что для любой метрики n-элементного множества существует O(\log n)-упаковка.

Удивительным образом, оказывается, что вопрос существования \beta-упаковки эквивалентен существованию \beta-вложения нашей метрики в пространство \mathbb{R}^m, которое снабжено метрикой l_1. Назовем функцию \sigma \colon V \to \mathbb{R}^m \beta-вложением метрики d, если для любой пары u, v \in V выполняются такие неравенства:

d(u, v) / \beta \leq \| \sigma(u) - \sigma(v) \|_{l_1} \leq d(u, v).

Несложно проверить, что \beta-упаковка существует тогда и только тогда, когда существует \beta-вложение.

А теперь самое интересное: оказывается для любой метрики d на n-элементном множестве существует O(\log n)-вложение в \mathbb{R}^{O(\log^2 n)}, снабженное метрикой l_1. Этот факт доказал Бургейн в 1985 году. Этот факт является технически сложным.

Таким образом, можно доказать оценку \alpha^* \leq f^* \cdot O(\log n). Если немного подшаманить, то можно ее чуть-чуть усилить — до O(\log k).

Реклама