Existe um algoritmo de aproximação de fator constante para o problema de coloração de retângulos 2D?

17

O problema que consideramos aqui é a extensão do conhecido problema de coloração por intervalo. Em vez de intervalos, consideramos retângulos com lados paralelos aos eixos. O objetivo é colorir os retângulos usando o número mínimo de cores, para que dois retângulos sobrepostos tenham cores diferentes.

Esse problema é conhecido por ser NP-difícil. Xin Han, Kazuo Iwama, Rolf Klein e Andrezej Lingas (Aproximando o conjunto independente máximo e a coloração mínima de vértices nos gráficos de caixa) deram uma aproximação de O (log n). Existe um algoritmo de aproximação melhor?

Sabemos que o problema de coloração de intervalo é resolvido em tempo polinomial pelo algoritmo de primeiro ajuste, considerando intervalos de acordo com os pontos finais esquerdos. No entanto, o algoritmo online de primeiro ajuste é 8-competitivo quando os intervalos aparecem em ordem arbitrária.

Qual é o desempenho do algoritmo de primeiro ajuste para o problema de coloração de retângulos? O que acontece com o algoritmo de primeiro ajuste quando os retângulos aparecem de acordo com o lado esquerdo (vertical)?

Agradeço desde já toda a ajuda nisto.

Soumitra
fonte

Respostas:

12

Como sugerido pela outra resposta, Ω(registron) limite inferior não é muito difícil de ver. Vamos fazer a varredura de baixo para cima com uma linha horizontal. A idéia é criar componentes que exijam um número cada vez maior de cores. Em particular, seja C(Eu) um gadget que tenha um retângulo superior com a cor Eu (ou seja, o primeiro ajuste atribuiria a cor Eu ). Claramente, C(1 1) é apenas um único retângulo. O componente C(2) é

Em geral, o componente C(k) é um retângulo com C(1 1),...,C(k-1 1) pendurado abaixo dele:

Agora, é fácil verificar se um algoritmo de ajuste inicial com varredura horizontal na parte inferior usaria k cores para colorir C(k) . No entanto, o gráfico de interseção de C(k) é apenas uma árvore e pode ser colorido por 2 cores. Agora, C(k) é apenas uma árvore de Fibonacci na estrutura, e, como tal, o número de nós em é 2O(k) , o que implica Ω(registron) lacuna.

Como existe um algoritmo simples que obtém uma aproximação O(registron) à coloração dos retângulos, isso pode ser difícil. Eu não sei.

Sariel Har-Peled
fonte
6

Tanto quanto eu sei, isso não é conhecido. Um artigo antigo de Asplund e Grunbaum (1960) mostra que, se o número de clique é 2, então o número cromático é no máximo 6 (e isso é apertado). Eu acho que deve ser fácil criar exemplos em que a diferença para o primeiro ajuste seja maior do que qualquer constante, pois as árvores podem ser representadas pelo gráfico de interseção de retângulos, e as árvores exigem cores log n por qualquer algoritmo on-line.

ipsofacto
fonte
3

Penso que os artigos Asplund, Grunbaum ou posteriores também mostram que o número cromático de gráficos de interseção de retângulos é no máximo O (k ^ 2), onde k é o tamanho da camarilha máxima ... no entanto, não se sabe exemplos que exigem mais do que linear em k número de cores.

ipsofacto
fonte