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

Беспроводные сети часто моделируются как ''графы единичных дисков'' (UDG): предполагается, что узлы находятся на двумерной евклидовой плоскости, при этом два узла соединены ребром, если расстояние между ними не превышает 1. Эта модель, безусловно, отражает присущую беспроводным сетям геометрическую природу. Однако для точного моделирования реальных беспроводных сетей графы единичных дисков кажутся слишком ограничивающими. Поэтому в [3, 4, 5] Куни коллеги рассматривают два обобщения модели графов единичных диск – ''графы с ограниченной независимостью'' (BIG) и ''графы единичных шаров'' (UBG). BIG представляет собой граф, в котором все локальные независимые множества имеют ограниченный размер. В частности, предполагается, что существует функция I(r), ограничивающая сверху размер наибольшего независимого множества каждой r-окрестности в графе. Заметим, что значение I(r) не зависит от n – размера сети. Если I(r) является полиномом от r, то говорят, что граф BIG полиномиально ограничен. UDG представляет собой BIG, в которых <math>I(r) \in O(r^2)</math>. Графы UBG являются естественным обобщением UDG. Пусть дано некоторое подлежащее метрическое пространство (V, d). Две вершины <math>u, v \in V</math> соединены ребром в том и только том случае, если <math>d(u, v) \le 1</math>. Если метрическое пространство (V, d) имеет константную размерность удвоения, то UBG – это полиномиально ограниченный BIG.

''(Размерность удвоения метрического пространства представляет собой логарифм от максимального количества шаров, необходимых для покрытия шара <math>B_r(x)</math> в метрическом пространстве шарами <math>B_{r/2}(y)</math> половинного радиуса)''

Первые алгоритмы для решения задач линейного программирования о покрытии и упаковке общего вида были предложены в [1, 10]. В [1] было показано, что можно найти решение, которое не более чем на коэффициент <math>1 + \varepsilon</math> отличается от оптимального, за <math>O(log^3(\rho n) / \varepsilon^3)</math> раундов, где <math>\rho</math> – отношение между наибольшим и наименьшим ненулевым коэффициентами LP. Результат был [1] улучшен и обобщен в [6 , 7], где было доказано следующее положение:

Теорема 4. За k раундов невозможно аппроксимировать задачу о минимальном вершинном покрытии лучше, чем коэффициентами Q{Allklk) и Q{nn{-llk Vfc). Это подразумевает нижние временные границы £?(log Л/loglog A) и £2(y/log n/log log n) для константных или даже полилогарифмических коэффициентов аппроксимации. Те же границы справедливы для задач о минимальном доминирующем множестве и о максимальном паросочетании, а также для лежащих в их основе LP.

Хотя теорема 4 показывает, что результаты, полученные в теоремах 1-3, близки к оптимальным для сетей с наихудшими топологиями, эти задачи могут оказаться намного более простыми, если ограничиться сетями, которые встречаются в реальности. В [3, 4, 5] показано, что приведенные выше результаты действительно можно улучшить, если положить, что граф сети является BIG или UBG с константной размерностью удвоения. В [5] был доказан следующий результат для UBG:

Теорема 5. Предположим, что сетевой граф G = (V, E) является UBG с базовой метрикой (V, d). Если (V, d) имеет константную размерность удвоения и если все узлы знают расстояния до своих соседей в G с точностью до константного множителя, то можно найти константные аппроксимации для минимального доминирующего множества, минимального вершинного покрытия, максимального паросочетания, а также для линейных программ (P) и (D) общего вида за O(log* n) раундов2.

Теорема 7. На полиномиально ограниченной BIG существует локальная схема аппроксимации, которая вычисляет (1 + ")-аппроксимацию для поиска минимального доминирующего множества за время O(log A log*(n)/£+ 1/"O(1)). Если сетевой граф является UBG с константной размерностью удвоения и если все узлы знают расстояния до своих соседей, то (1 + ")-аппроксимация может быть вычислена за 0(log*(n)/£ + 1/"O(1)) раундов.