Approximation algorithms for maximum independent set of pseudo-disks. (English) Zbl 1248.05135
Summary: We present approximation algorithms for maximum independent set of pseudo-disks in the plane, both in the weighted and unweighted cases. For the unweighted case, we prove that a local-search algorithm yields a PTAS. For the weighted case, we suggest a novel rounding scheme based on an LP relaxation of the problem, which leads to a constant-factor approximation.
Most previous algorithms for maximum independent set (in geometric settings) relied on packing arguments that are not applicable in this case. As such, the analysis of both algorithms requires some new combinatorial ideas, which we believe to be of independent interest.
Most previous algorithms for maximum independent set (in geometric settings) relied on packing arguments that are not applicable in this case. As such, the analysis of both algorithms requires some new combinatorial ideas, which we believe to be of independent interest.
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 68W25 | Approximation algorithms |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05B25 | Combinatorial aspects of finite geometries |
Keywords:
Fréchet distance; approximation algorithms; realistic input models; polynomial-time approximation scheme; PTASReferences:
| [1] | Afshani, P.; Chan, T. M., Dynamic connectivity for axis-parallel rectangles, No. 4168, 16-27 (2006) · Zbl 1131.68422 |
| [2] | Agarwal, P.K., Mustafa, N.H.: Independent set of intersection graphs of convex objects in 2D. Comput. Geom., Theory Appl. 34(2), 83-95 (2006) · Zbl 1153.68513 · doi:10.1016/j.comgeo.2005.12.001 |
| [3] | Agarwal, P.K., Aronov, B., Chan, T.M., Sharir, M.: On levels in arrangements of lines, segments, planes, and triangles. Discrete Comput. Geom. 19, 315-331 (1998) · Zbl 0899.68106 · doi:10.1007/PL00009348 |
| [4] | Agarwal, P.K., van Kreveld, M., Suri, S.: Label placement by maximum independent set in rectangles. Comput. Geom., Theory Appl. 11, 209-218 (1998) · Zbl 0921.68100 · doi:10.1016/S0925-7721(98)00028-5 |
| [5] | Agarwal, P. K.; Pach, J.; Sharir, M.; Goodman, J. E. (ed.); Pach, J. (ed.); Pollack, R. (ed.), State of the union—of geometric objects, No. 453, 9-48 (2008), Providence · Zbl 1155.52017 · doi:10.1090/conm/453/08794 |
| [6] | Alon, N., Spencer, J.H.: The Probabilistic Method, 2nd edn. Wiley-Interscience, New York (2000) · Zbl 0996.05001 · doi:10.1002/0471722154 |
| [7] | Arora, S.: Polynomial time approximation schemes for Euclidean TSP and other geometric problems. J. Assoc. Comput. Mach. 45(5), 753-782 (1998) · Zbl 1064.90566 · doi:10.1145/290179.290180 |
| [8] | Asplund, E., Grübaum, B.: On a coloring problem. Math. Scand. 8, 181-188 (1960) · Zbl 0095.17002 |
| [9] | Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. Assoc. Comput. Mach. 41, 153-180 (1994) · Zbl 0807.68067 · doi:10.1145/174644.174650 |
| [10] | Bar-Yehuda, R., Bendel, K., Freund, A., Rawitz, D.: Local ratio: A unified framework for approximation algorithms. In memoriam: Shimon Even 1935-2004. ACM Comput. Surv. 36, 422-463 (2004) · doi:10.1145/1041680.1041683 |
| [11] | Berman, P., Fujito, T.: On approximation properties of the independent set problem for low degree graphs. Theor. Comput. Sci. 32(2), 115-132 (1999) · Zbl 0916.68109 · doi:10.1007/s002240000113 |
| [12] | Berman, P., DasGupta, B., Muthukrishnan, S., Ramaswami, S.: Efficient approximation algorithms for tiling and packing problems with rectangles. J. Algorithms 41, 443-470 (2001) · Zbl 0999.68248 · doi:10.1006/jagm.2001.1188 |
| [13] | Brönnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14, 263-279 (1995) · Zbl 0841.68122 · doi:10.1007/BF02570718 |
| [14] | Chalermsook, P.; Chuzhoy, J., Maximum independent set of rectangles, 892-901 (2009) · Zbl 1423.90216 |
| [15] | 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 |
| [16] | Chan, T.M.: A note on maximum independent sets in rectangle intersection graphs. Inf. Process. Lett. 89, 19-23 (2004) · Zbl 1178.68674 · doi:10.1016/j.ipl.2003.09.019 |
| [17] | Chan, T. M.; Har-Peled, S., Approximation algorithms for maximum independent set of pseudo-disks, 333-340 (2009) · Zbl 1388.68285 · doi:10.1145/1542362.1542420 |
| [18] | Chekuri, C., Vondrák, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: Proc. 43rd Annu. ACM Sympos. Theory Comput. (2011, to appear) · Zbl 1288.90081 |
| [19] | Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4, 387-421 (1989) · Zbl 0681.68060 · doi:10.1007/BF02187740 |
| [20] | Clarkson, K.L., Varadarajan, K.R.: Improved approximation algorithms for geometric set cover. Discrete Comput. Geom. 37(1), 43-58 (2007) · Zbl 1106.68121 · doi:10.1007/s00454-006-1273-8 |
| [21] | Efrat, A., Katz, M.J., Nielsen, F., Sharir, M.: Dynamic data structures for fat objects and their applications. Comput. Geom., Theory Appl. 15, 215-227 (2000) · Zbl 0952.68147 · doi:10.1016/S0925-7721(99)00059-0 |
| [22] | Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Comput. 34(6), 1302-1323 (2005) · Zbl 1081.68031 · doi:10.1137/S0097539702402676 |
| [23] | Even, G., Rawitz, D., Shahar, S.: Hitting sets when the VC-dimension is small. Inf. Process. Lett. 95(2), 358-362 (2005) · Zbl 1184.68632 · doi:10.1016/j.ipl.2005.03.010 |
| [24] | Fox, J.; Pach, J., Computing the independence number of intersection graphs, 1161-1165 (2011) · Zbl 1377.68275 |
| [25] | Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput. 16(6), 1004-1022 (1987) · Zbl 0654.68087 · doi:10.1137/0216064 |
| [26] | Halldórsson, M. M., Approximations of independent sets in graphs, 1-13 (1998) · Zbl 0903.05044 |
| [27] | Hastad, J.: Clique is hard to approximate within n1−ε. Acta Math. 182, 105-142 (1996) · Zbl 0989.68060 · doi:10.1007/BF02392825 |
| [28] | Kedem, K., Livne, R., Pach, J., Sharir, M.: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discrete Comput. Geom. 1, 59-71 (1986) · Zbl 0594.52004 · doi:10.1007/BF02187683 |
| [29] | Koufogiannakis, C.; Young, N. E., Beating simplex for fractional packing and covering linear programs, 494-506 (2007) |
| [30] | Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 177-189 (1979) · Zbl 0432.05022 · doi:10.1137/0136016 |
| [31] | Long, P. M., Using the pseudo-dimension to analyze approximation algorithms for integer programming, No. 2125, 26-37 (2001) · Zbl 1018.90027 |
| [32] | Marathe, M.V., Breu, H., Hunt, H.B. III, Ravi, S.S., Rosenkrantz, D.J.: Simple heuristics for unit disk graphs. Networks 25, 59-68 (1995) · Zbl 0821.90128 · doi:10.1002/net.3230250205 |
| [33] | Matoušek, J.: Reporting points in halfspaces. Comput. Geom., Theory Appl. 2(3), 169-186 (1992) · Zbl 0772.68105 · doi:10.1016/0925-7721(92)90006-E |
| [34] | Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995) · Zbl 0849.68039 |
| [35] | Mustafa, N. H.; Ray, S., PTAS for geometric hitting set problems via local search, 17-22 (2009) · Zbl 1380.68403 · doi:10.1145/1542362.1542367 |
| [36] | Nieberg, T.; Hurink, J.; Kern, W., A robust PTAS for maximum weight independent set in unit disk graphs, No. 3353, 214-221 (2005) · Zbl 1112.68427 · doi:10.1007/978-3-540-30559-0_18 |
| [37] | Pyrga, E.; Ray, S., New existence proofs for ε-nets, 199-207 (2008) · Zbl 1221.52016 |
| [38] | Smith, W. D.; Wormald, N. C., Geometric separator theorems and applications, 232-243 (1998) |
| [39] | Varadarajan, K., Weighted geometric set cover via quasi-uniform sampling, 641-648 (2010) · Zbl 1293.68300 |
| [40] | Whitesides, S., Zhao, R.: k-admissible collections of Jordan curves and offsets of circular arc figures. Technical Report SOCS 90.08, McGill Univ., Montreal, Quebec (1990) |
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.
