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.
fonte