Существует ли алгоритм аппроксимации постоянного множителя для задачи раскраски 2D-прямоугольника?

17

Задача, которую мы здесь рассматриваем, - это расширение хорошо известной проблемы интервальной раскраски. Вместо интервалов мы рассматриваем прямоугольники, стороны которых параллельны осям. Цель состоит в том, чтобы закрасить прямоугольники минимальным количеством цветов, чтобы любые два перекрывающихся прямоугольника были назначены разным цветам.

Эта проблема, как известно, NP-сложная. Синь Хань, Казуо Ивама, Рольф Кляйн и Андрэйзей Лингас (Аппроксимация максимального независимого множества и минимальной окраски вершин на блочных графах) дали приближение O (log n). Есть ли лучший алгоритм приближения?

Мы знаем, что проблема интервальной раскраски решается за полиномиальное время алгоритмом первой подгонки с учетом интервалов в соответствии с их левыми конечными точками. Тем не менее, первый подход онлайн алгоритм является 8-конкурентным, когда интервалы появляются в произвольном порядке.

Какова эффективность алгоритма первого соответствия для задачи раскраски прямоугольника? Что происходит с алгоритмом первого соответствия, когда прямоугольники появляются в соответствии с их левой (вертикальной) стороной?

Заранее спасибо за любую помощь в этом.

Soumitra
источник

Ответы:

12

Как следует из другого ответа, нижнюю границу не так сложно увидеть. Давайте сделаем широкое основание с горизонтальной линией. Идея заключается в создании компонентов, которые требуют все большего и большего количества цветов. В частности, позвольте быть гаджетом, у которого есть верхний прямоугольник с цветом (то есть, первая подгонка назначит ему цвет ). Ясно, что - это просто один прямоугольник. Компонент являетсяΩ(журналN)С(я)яяС(1)С(2)

В общем случае компонент представляет собой прямоугольник с висящими под ним:С(К)С(1),...,С(К-1)

Теперь легко проверить, что алгоритм подгонки вначале с горизонтальным смещением снизу будет использовать цветов для цвета . Тем не менее, граф пересечений - это просто дерево, и его можно раскрасить цветами. Теперь C ( k ) - это просто дерево Фибоначчи по структуре, и поэтому число узлов в нем равно 2 O ( k ) , что влечет зазор Ω ( log n ) .КС(К)С(К)2С(К)2О(К)Ω(журналN)

Поскольку существует простой алгоритм, который получает О(журналN) приближение к раскраске прямоугольников, это может быть сложно. Я не знаю.

Сариэль Хар-Пелед
источник
6

Насколько я знаю, это не известно. В старой статье Асплунда и Грюнбаума (1960-е) показано, что если число кликов равно 2, то хроматическое число не более 6 (и это очень мало). Я думаю, что должно быть легко найти примеры, где разрыв для первого соответствия больше, чем любая константа, поскольку деревья могут быть представлены графом пересечений прямоугольников, а деревья требуют log n цветов любым онлайн-алгоритмом.

ipsofacto
источник
3

Я думаю, что бумага Асплунда, Грюнбаума или более поздние статьи также показывают, что хроматическое число графов пересечения прямоугольников не больше O (k ^ 2), где k - размер максимальной клики ... однако неизвестно примеры, которые требуют больше, чем линейное число k цветов.

ipsofacto
источник