Archive for Май 2011

Минимальная несбалансированность

Май 10, 2011

Представьте себе двудольный граф, в каждой доле которого ровно n вершин. Напишем на вершинах левой доли плюс-минус единицы. Теперь для каждой вершины правой доли посчитаем модуль суммы чисел соседей. Среди этих модулей выберем максимальный. Будем интересоваться разметкой плюс-минус единицами, которая минимизирует этот максимум.

С помощью вероятностного метода легко доказать, что существует разметка такая, что максимум модуля равен O(\sqrt{n \log n}). С помощью опять же вероятностного метода легко показать, что найдется граф такой, что этот максимум при любой разметке равен \Omega(\sqrt{n}). Таким образом, остается небольшой зазор между нижней и верхней оценками.

Оказывается, что точный ответ — \Theta(\sqrt{n}). Это знаменитая теорема Спенсера (1985 год). Хорошо написанное доказательство (которое использует забавные теоретико-информационные соображения) есть в Алоне-Спенсере. Доказательство неконструктивное, то есть оно не дает полиномиального (вероятностного) алгоритма для построения такой разметки.

Недавно Bansal (FOCS ’10) восполнил этот пробел — в статье «Constructive Algorithms for Discrepancy Minimization» приведен полиномиальный алгоритм для поиска таких разметок. К сожалению, на первый взгляд он довольно сложен.

Реклама