Algorithms for Intersection Graphs for $t$-Intervals and $t$-Pseudodisks

by Chandra Chekuri and Tanmay Inamdar

Theory of Computing, Volume 18(18), pp. 1-19, 2022

Bibliography with links to cited articles

[1]   Anna Adamaszek, Sariel Har-Peled, and Andreas Wiese: Approximation schemes for independent set and sparse subsets of polygons. J. ACM, 66(4):29:1–40, 2019. [doi:10.1145/3326122]

[2]   Anna Adamaszek and Andreas Wiese: Approximation schemes for maximum weight independent set of rectangles. In Proc. 54th FOCS, pp. 400–409. IEEE Comp. Soc., 2013. [doi:10.1109/FOCS.2013.50]

[3]   Pankaj K. Agarwal, János Pach, and Micha Sharir: State of the union (of geometric objects): A review. In Jacob E. Goodman, János Pach, and Richard Pollack, editors, Surveys in Discrete and Computational Geometry: Twenty Years Later, pp. 9–48. Amer. Math. Soc., 2007. Volume DOI.

[4]   Boris Aronov, Mark de Berg, Esther Ezra, and Micha Sharir: Improved bounds for the union of locally fat objects in the plane. SIAM J. Comput., 43(2):543–572, 2014. [doi:10.1137/120891241]

[5]   Boris Aronov, Anirudh Donakonda, Esther Ezra, and Rom Pinchasi: On pseudo-disk hypergraphs. Comput. Geom., 92:101687, 2021. [doi:10.1016/j.comgeo.2020.101687]

[6]   Nikhil Bansal, Anupam Gupta, and Guru Guruganesh: On the Lovász theta function for independent sets in sparse graphs. SIAM J. Comput., 47(3):1039–1055, 2018. [doi:10.1137/15M1051002]

[7]   Nikhil Bansal and Kirk Pruhs: Weighted geometric set multi-cover via quasi-uniform sampling. J. Comput. Geom., 7(1):221–236, 2016. [doi:10.20382/jocg.v7i1a11]

[8]   Reuven Bar-Yehuda, Magnús M. Halldórsson, Joseph Naor, Hadas Shachnai, and Irina Shapira: Scheduling split intervals. SIAM J. Comput., 36(1):1–15, 2006. [doi:10.1137/S0097539703437843]

[9]   Reuven Bar-Yehuda and Dror Rawitz: Using fractional primal-dual to schedule split intervals with demands. Discr. Optimization, 3(4):275–287, 2006. [doi:10.1016/j.disopt.2006.05.010]

[10]   Ayelet Butman, Danny Hermelin, Moshe Lewenstein, and Dror Rawitz: Optimization problems in multiple-interval graphs. ACM Trans. Algorithms, 6(2):40:1–18, 2010. [doi:10.1145/1721837.1721856]

[11]   Timothy M. Chan, Elyot Grant, Jochen Könemann, and Malcolm Sharpe: Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In Proc. 23rd Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’12), pp. 1576–1585. SIAM, 2012. [doi:10.1137/1.9781611973099.125]

[12]   Timothy M. Chan and Sariel Har-Peled: Approximation algorithms for Maximum Independent Set of pseudo-disks. Discr. Comput. Geom., 48(2):373–392, 2012. [doi:10.1007/s00454-012-9417-5]

[13]   Chandra Chekuri, Kenneth L. Clarkson, and Sariel Har-Peled: On the set multicover problem in geometric settings. ACM Trans. Algorithms, 9(1):9:1–17, 2012. [doi:10.1145/2390176.2390185]

[14]   Chandra Chekuri, Kent Quanrud, and Zhao Zhang: On approximating partial set cover and generalizations, 2019. [arXiv:1907.04413]

[15]   Kenneth L. Clarkson and Kasturi R. Varadarajan: Improved approximation algorithms for geometric set cover. Discr. Comput. Geom., 37(1):43–58, 2007. [doi:10.1007/s00454-006-1273-8]

[16]   Irit Dinur, Venkatesan Guruswami, Subhash Khot, and Oded Regev: A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM J. Comput., 34(5):1129–1146, 2005. [doi:10.1137/S0097539704443057]

[17]   Alina Ene, Sariel Har-Peled, and Benjamin Raichel: Geometric packing under nonuniform constraints. SIAM J. Comput., 46(6):1745–1784, 2017. [doi:10.1137/120898413]

[18]   Uriel Feige: A threshold of lnn for approximating set cover. J. ACM, 45(4):634–652, 1998. [doi:10.1145/285055.285059]

[19]   Uriel Feige: Approximating maximum clique by removing subgraphs. SIAM J. Discr. Math., 18(2):219–225, 2004. [doi:10.1137/S089548010240415X]

[20]   Matt Gibson and Imran A. Pirwani: Algorithms for dominating set in disk graphs: Breaking the log n barrier. In Proc. 18th Eur. Symp. Algorithms (ESA’10), pp. 243–254. Springer, 2010. [doi:10.1007/978-3-642-15775-2_21]

[21]   Jerrold R. Griggs and Douglas B. West: Extremal values of the interval number of a graph. SIAM J. Algebr. Discr. Methods, 1(1):1–7, 1980. [doi:10.1137/0601001]

[22]   Johan Håstad: Clique is hard to approximate within n1-ε. Acta Math., 182(1):105–142, 1999. [doi:10.1007/BF02392825]

[23]   Dorit S. Hochbaum and Asaf Levin: Cyclical scheduling and multi-shift scheduling: Complexity and approximation algorithms. Discr. Optimization, 3(4):327–340, 2006. [doi:10.1016/j.disopt.2006.02.002]

[24]   Tanmay Inamdar and Kasturi R. Varadarajan: On partial covering for geometric set systems. In Proc. 34th Internat. Symp. Comput. Geom. (SoCG’18), pp. 47:1–14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.SoCG.2018.47]

[25]   Frank Kammer and Torsten Tholey: Approximation algorithms for intersection graphs. Algorithmica, 68(2):312–336, 2014. Preliminary version in [26]. [doi:10.1007/s00453-012-9671-1]

[26]   Frank Kammer, Torsten Tholey, and Heiko Voepel: Approximation algorithms for intersection graphs. In Proc. 13th Internat. Workshop on Approximation Algorithms for Combinat. Opt. Probl. (APPROX’10), pp. 260–273. Springer, 2010. [doi:10.1007/978-3-642-15369-3_20]

[27]   Klara Kedem, Ron Livne, János Pach, and Micha Sharir: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discr. Comput. Geom., 1:59–70, 1986. [doi:10.1007/BF02187683]

[28]   Subhash Khot: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp. 767–775. ACM Press, 2002. [doi:10.1145/509907.510017]

[29]   Subhash Khot and Oded Regev: Vertex cover might be hard to approximate to within 2-ϵ. J. Comput. System Sci., 74(3):335–349, 2008. [doi:10.1016/j.jcss.2007.06.019]

[30]   Dana Moshkovitz: The Projection Games Conjecture and the NP-hardness of lnn-approximating set-cover. Theory of Computing, 11(7):221–235, 2015. [doi:10.4086/toc.2015.v011a007]

[31]   Nabil H. Mustafa and Kasturi R. Varadarajan: Epsilon-approximations and epsilon-nets. In Jacob E. Goodman, Joseph O’Rourke, and Csaba D. Tóth, editors, Handbook of Discrete and Computational Geometry. Chapman and Hall/CRC, 3rd edition, 2017. Taylor–Francis. [arXiv:1702.03676]

[32]   Aniket Basu Roy, Sathish Govindarajan, Rajiv Raman, and Saurabh Ray: Packing and covering with non-piercing regions. Discr. Comput. Geom., 60(2):471–492, 2018. [doi:10.1007/s00454-018-9983-2]

[33]   Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency. 2003. Springer.

[34]   William P. Thurston: The Geometry and Topology of Three-Manifolds. 1979. Princeton U. Press.

[35]   Kasturi R. Varadarajan: Weighted geometric set cover via quasi-uniform sampling. In Proc. 42nd STOC, pp. 641–648. ACM Press, 2010. [doi:10.1145/1806689.1806777]

[36]   Vijay V. Vazirani: Approximation Algorithms. Springer, 2013.

[37]   David P. Williamson and David B. Shmoys: The Design of Approximation Algorithms. Cambridge Univ. Press, 2011. LINK.

[38]   Yuli Ye and Allan Borodin: Elimination graphs. ACM Trans. Algorithms, 8(2):14:1–23, 2012. [doi:10.1145/2151171.2151177]

[39]   David Zuckerman: Linear degree extractors and the inapproximability of Max Clique and chromatic number. Theory of Computing, 3(6):103–128, 2007. Preliminary version in STOC’06. [doi:10.4086/toc.2007.v003a006]