Coloring and maximum independent set of rectangles. (English) Zbl 1343.90076
Goldberg, Leslie Ann (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 14th international workshop, APPROX 2011, and 15th international workshop, RANDOM 2011, Princeton, NJ, USA, August 17–19, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22934-3/pbk). Lecture Notes in Computer Science 6845, 123-134 (2011).
Summary: 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 \(\sigma (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 \(\sigma (q) \leq 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 \(\sigma (q)\) that significantly improves the known bounds for a broad class of instances.
The bound \(\sigma (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 the author and J. Chuzhoy [“Maximum independent set of rectangles”, in: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 892–901 (2009)], 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.
For the entire collection see [Zbl 1219.68018].
The bound \(\sigma (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 the author and J. Chuzhoy [“Maximum independent set of rectangles”, in: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 892–901 (2009)], 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.
For the entire collection see [Zbl 1219.68018].
References:
| [1] | Agarwal, P.K., van Kreveld, M.J., Suri, S.: Label placement by maximum independent set in rectangles. Comput. Geom. 11(3-4), 209–218 (1998) · Zbl 0921.68100 · doi:10.1016/S0925-7721(98)00028-5 |
| [2] | Ahlswede, R., Karapetyan, I.: Intersection graphs of rectangles and segments. In: Ahlswede, R., Bäumer, L., Cai, N., Aydinian, H., Blinovsky, V., Deppe, C., Mashurian, H. (eds.) General Theory of Information Transfer and Combinatorics. LNCS, vol. 4123, pp. 1064–1065. Springer, Heidelberg (2006) · Zbl 1158.05328 · doi:10.1007/11889342_68 |
| [3] | Asplund, E., Grunbaum, B.: On a coloring problem. Math. Scand. 8, 181–188 (1960) · Zbl 0095.17002 · doi:10.7146/math.scand.a-10607 |
| [4] | Bar-Yehuda, R., Hermelin, D., Rawitz, D.: Minimum vertex cover in rectangle graphs. In: de Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol. 6346, pp. 255–266. Springer, Heidelberg (2010) · Zbl 1287.05143 · doi:10.1007/978-3-642-15775-2_22 |
| [5] | Berman, P., DasGupta, B., Muthukrishnan, S., Ramaswami, S.: Improved approximation algorithms for rectangle tiling and packing. In: SODA, pp. 427–436 (2001) · Zbl 1113.68635 |
| [6] | Bielecki, A.: Problem 56. Colloq. Math. 1, 333 (1948) |
| [7] | Bonsma, P., Schulz, J., Wiese, A.: A constant factor approximation algorithm for unsplittable flow on paths. In: Arxiv (2011) · Zbl 1292.68162 · doi:10.1109/FOCS.2011.10 |
| [8] | Chalermsook, P., Chuzhoy, J.: Maximum independent set of rectangles. In: SODA, pp. 892–901 (2009) · doi:10.1137/1.9781611973068.97 |
| [9] | Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms 46(2), 178–189 (2003) · Zbl 1030.68093 · doi:10.1016/S0196-6774(02)00294-8 |
| [10] | Chan, T.M.: A note on maximum independent sets in rectangle intersection graphs. Inf. Process. Lett. 89(1), 19–23 (2004) · Zbl 1178.68674 · doi:10.1016/j.ipl.2003.09.019 |
| [11] | Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. In: Symposium on Computational Geometry, pp. 333–340 (2009) · Zbl 1388.68285 · doi:10.1145/1542362.1542420 |
| [12] | Christodoulou, G., Elbassioni, K., Fouz, M.: Truthful mechanisms for exhibitions. In: Saberi, A. (ed.) WINE 2010. LNCS, vol. 6484, pp. 170–181. Springer, Heidelberg (2010) · doi:10.1007/978-3-642-17572-5_14 |
| [13] | Doerschler, J.S., Freeman, H.: A rule-based system for dense-map name placement. Commun. ACM 35(1), 68–79 (1992) · doi:10.1145/129617.129620 |
| [14] | Erdös, P.: Graph theory and probability. Canadian J. of Mathematics 11, 34–38 (1959) · Zbl 0084.39602 · doi:10.4153/CJM-1959-003-9 |
| [15] | Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric graphs. In: SODA, pp. 671–679 (2001) · Zbl 0988.65020 |
| [16] | Fowler, R.J., Paterson, M., Tanimoto, S.L.: Optimal packing and covering in the plane are np-complete. Inf. Process. Lett. 12(3), 133–137 (1981) · Zbl 0469.68053 · doi:10.1016/0020-0190(81)90111-3 |
| [17] | Fukuda, T., Morimoto, Y., Morishita, S., Tokuyama, T.: Data mining with optimized two-dimensional association rules. ACM Trans. Database Syst. 26(2), 179–213 (2001) · Zbl 1136.68381 · doi:10.1145/383891.383893 |
| [18] | Hendler, C.: Schranken fur farbungs-und cliquenuberdeckungszahl geometrisch represdntierbarer graphen. Master Thesis (1998) |
| [19] | Imai, H., Asano, T.: Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J. Algorithms 4(4), 310–323 (1983) · Zbl 0548.68067 · doi:10.1016/0196-6774(83)90012-3 |
| [20] | Khanna, S., Muthukrishnan, S., Paterson, M.: On approximating rectangle tiling and packing. In: SODA, pp. 384–393 (1998) · Zbl 0938.68928 |
| [21] | Kostochka, A.V.: Coloring intersection graphs of geometric figures with a given clique number. Contemporary Mathematics 342 (2004) · Zbl 1064.05059 · doi:10.1090/conm/342/06137 |
| [22] | Lent, B., Swami, A.N., Widom, J.: Clustering association rules. In: ICDE, pp. 220–231 (1997) · doi:10.1109/ICDE.1997.581756 |
| [23] | Lewin-Eytan, L., Naor, J(S.), Orda, A.: Routing and admission control in networks with advance reservations. In: Jansen, K., Leonardi, S., Vazirani, V.V. (eds.) APPROX 2002. LNCS, vol. 2462, pp. 215–228. Springer, Heidelberg (2002) · Zbl 1013.90122 · doi:10.1007/3-540-45753-4_19 |
| [24] | Nielsen, F.: Fast stabbing of boxes in high dimensions. Theor. Comput. Sci. 246(1-2), 53–72 (2000) · Zbl 0949.68147 · doi:10.1016/S0304-3975(98)00336-3 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
