Coloring and maximum independent set of rectangles

Parinya Chalermsook*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

16 Citations (Scopus)

Abstract

In this paper, we consider two geometric optimization problems: Rectangle Coloring problem (RCOL) and Maximum Independent Set of Rectangles (MISR). In RCOL, we are given a collection of n rectangles in the plane where overlapping rectangles need to be colored differently, and the goal is to find a coloring using minimum number of colors. Let q be the maximum clique size of the instance, i.e. the maximum number of rectangles containing the same point. We are interested in bounding the ratio σ(q) between the total number of colors used and the clique size. This problem was first raised by graph theory community in 1960 when the ratio of σ(q) ≤ O(q) was proved. Over decades, except for special cases, only the constant in front of q has been improved. In this paper, we present a new bound for σ(q) that significantly improves the known bounds for a broad class of instances. The bound σ(q) has a strong connection with the integrality gap of natural LP relaxation for MISR, in which the input is a collection of rectangles where each rectangle is additionally associated with non-negative weight, and our objective is to find a maximum-weight independent set of rectangles. MISR has been studied extensively and has applications in various areas of computer science. Our new bounds for RCOL imply new approximation algorithms for a broad class of MISR, including (i) O(log log n) approximation algorithm for unweighted MISR, matching the result by Chalermsook and Chuzhoy, and (ii) O(log log n)-approximation algorithm for the MISR instances arising in the Unsplittable Flow Problem on paths. Our technique builds on and generalizes past works.

Original languageEnglish
Title of host publicationApproximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings
Pages123-134
Number of pages12
Volume6845 LNCS
DOIs
Publication statusPublished - 2011
MoE publication typeA4 Conference publication
EventInternational Workshop on Approximation Algorithms for Combinatorial Optimization Problems - Princeton, United States
Duration: 17 Aug 201119 Aug 2011
Conference number: 14

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6845 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Workshop

WorkshopInternational Workshop on Approximation Algorithms for Combinatorial Optimization Problems
Abbreviated titleAPPROX
Country/TerritoryUnited States
CityPrinceton
Period17/08/201119/08/2011

Fingerprint

Dive into the research topics of 'Coloring and maximum independent set of rectangles'. Together they form a unique fingerprint.

Cite this