Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint

by Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Joseph S. B. Mitchell, and Nabil H. Mustafa

Theory of Computing, Volume 22(1172), pp. 1-38, 2026

Bibliography with links to cited articles

[1]   Sanjeev Arora: Polynomial time approximation schemes for Euclidean Traveling Salesman and other geometric problems. J. ACM, 45(5):753–782, 1998. Preliminary version in FOCS’96. [doi:10.1145/290179.290180]

[2]   Yair Bartal, Lee-Ad Gottlieb, and Robert Krauthgamer: The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. SIAM J. Comput., 45(4):1563–1581, 2016. Preliminary version in STOC’12. [doi:10.1137/130913328, arXiv:1112.0699]

[3]   Gruia Călinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput., 40(6):1740–1766, 2011. [doi:10.1137/080733991]

[4]   Erin W. Chambers, Sándor P. Fekete, Hella-Franziska Hoffmann, Dimitri Marinakis, Joseph S. B. Mitchell, Venkatesh Srinivasan, Ulrike Stege, and Sue Whitesides: Connecting a set of circles with minimum sum of radii. Comput. Geom., 68:62–76, 2018. Special issue in memory of Ferran Hurtado. Preliminary version in WADS’11. [doi:10.1016/j.comgeo.2017.06.002, arXiv:1105.0791]

[5]   T.-H. Hubert Chan and Shaofeng H.-C. Jiang: Reducing curse of dimensionality: Improved PTAS for TSP (with neighborhoods) in doubling metrics. ACM Trans. Algorithms, 14(9):1–18, 2018. Preliminary version in SODA’16. [doi:10.1145/3158232]

[6]   Steven Chaplick, Minati De, Alexander Ravsky, and Joachim Spoerhase: Approximation schemes for geometric coverage problems. In Proc. 26th Eur. Symp. Algorithms (ESA’18), pp. 17:1–15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ESA.2018.17, arXiv:1607.06665]

[7]   Brent N. Clark, Charles J. Colbourn, and David S. Johnson: Unit disk graphs. Discr. Math., 86(1–3):165–177, 1990. [doi:10.1016/0012-365X(90)90358-O]

[8]   Adrian Dumitrescu and Joseph S. B. Mitchell: Approximation algorithms for TSP with neighborhoods in the plane. J. Algorithms, 48(1):135–159, 2003. Preliminary version in SODA’01. [doi:10.1016/S0196-6774(03)00047-6, arXiv:1703.01640]

[9]   Adrian Dumitrescu and Csaba D. Tóth: Constant-factor approximation for TSP with disks. In Martin Loebl, Jaroslav Nešetřil, and Robin Thomas, editors, A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek, pp. 375–390. Springer, Cham, 2017. [doi:10.1007/978-3-319-44479-6_15, arXiv:1506.07903]

[10]   Khaled M. Elbassioni, Aleksei V. Fishkin, and René Sitters: On approximating the TSP with intersecting neighborhoods. In Proc. Internat. Symp. on Algorithms and Computation (ISAAC’06), pp. 213–222. Springer, 2006. [doi:10.1007/11940128_23]

[11]   Khaled M. Elbassioni, Aleksei V. Fishkin, and René Sitters: Approximation algorithms for the Euclidean traveling salesman problem with discrete and continuous neighborhoods. Internat. J. Comput. Geom. Appl., 19(2):173–193, 2009. [doi:10.1142/S0218195909002897]

[12]   Corinne Feremans and Alexander Grigoriev: Approximation schemes for the generalized geometric problems with geographic clustering. In Proc. 21st Europ. Workshop on Comput. Geometry (EuroCG’05), pp. 101–102, 2005. TU Eindhoven.

[13]   Stefan Funke, Alex Kesselman, Fabian Kuhn, Zvi Lotker, and Michael Segal: Improved approximation algorithms for connected sensor cover. Wireless Networks, 13(2):153–164, 2007. Preliminary version in ADHOC-NOW’04. [doi:10.1007/s11276-006-3724-9]

[14]   Michael M. Garey and David S. Johnson: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math., 32(4):826–834, 1977. [doi:10.1137/0132071]

[15]   Himanshu Gupta, Zongheng Zhou, Samir R. Das, and Quinyi Gu: Connected sensor cover: Self-organization of sensor networks for efficient query execution. IEEE/ACM Transactions on Networks, 14(1):55–67, 2006. Preliminary version in MOBIHOC’03. [doi:10.1109/TNET.2005.863478]

[16]   Sariel Har-Peled: Being fat and friendly is not enough, 2009. [arXiv:0908.2369]

[17]   Dorit S. Hochbaum and Anu Pathria: Node-optimal connected k-subgraphs. Technical report, UC Berkeley, 1994. Author’s website.

[18]   Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Joseph S. B. Mitchell, and Nabil H. Mustafa: Maximizing covered area in the Euclidean plane with connectivity constraint. In Proc. 22nd Internat. Conf. on Approximation Algorithms for Combinat. Opt. Probl. (APPROX’19), pp. 32:1–21. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.APPROX-RANDOM.2019.32]

[19]   Harry B. Hunt, Madhav V. Marathe, Venkatesh Radhakrishnan, Shankar S. Ravi, Daniel J. Rosenkrantz, and Richard E. Stearns: NC-approximation schemes for NP- and PSPACE-Hard problems for geometric graphs. J. Algorithms, 26(2):238–274, 1998. [doi:10.1006/jagm.1997.0903]

[20]   Koushik Kar and Suman Banerjee: Node placement for connected coverage in sensor networks. Poster, Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt’03), 2003 (2 pages). HAL.

[21]   Samir Khuller, Manish Purohit, and Kanthi K. Sarpatwar: Analyzing the optimal neighborhood: Algorithms for partial and budgeted connected dominating set problems. SIAM J. Discr. Math., 34(1):251–270, 2020. Preliminary version in SODA’14. [doi:10.1137/18M1212094, arXiv:1311.2309]

[22]   Ariel Kulik, Hadas Shachnai, and Tami Tamir: Maximizing submodular set functions subject to multiple linear constraints. In Proc. 20th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’09), pp. 545–554. SIAM, 2009. [doi:10.1137/1.9781611973068.60]

[23]   Tung-Wei Kuo, Kate Ching-Ju Lin, and Ming-Jer Tsai: Maximizing submodular set function with connectivity constraint: Theory and application to networks. IEEE/ACM Transactions on Networks, 23(2):533–546, 2015. Preliminary version in INFOCOM’13. [doi:10.1109/TNET.2014.2301816]

[24]   Ioannis Lamprou, Ioannis Sigalas, and Vassilis Zissimopoulos: Improved budgeted connected domination and budgeted edge-vertex domination. Theoret. Comput. Sci., 858:1–12, 2020. Preliminary version in IWOCA’20. [doi:10.1016/j.tcs.2021.01.030, arXiv:1907.06576]

[25]   Jon Lee, Maxim Sviridenko, and Jan Vondrák: Submodular maximization over multiple matroids via generalized exchange properties. Math. Oper. Res., 35(4):795–806, 2010. Preliminary version in APPROX’09. [doi:10.1287/moor.1100.0463]

[26]   Madhav V. Marathe, Heinz Breu, Harry B. Hunt III, Shankar S. Ravi, and Daniel J. Rosenkrantz: Simple heuristics for unit disk graphs. Networks, 25(2):59–68, 1995. [doi:10.1002/net.3230250205]

[27]   Tomomi Matsui: Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs. In Proc. 2nd Japanese Conf. Discr. Comput. Geometry (JCDCG’98), pp. 194–200. Springer, 1998. [doi:10.1007/978-3-540-46515-7_16]

[28]   Joseph S. B. Mitchell: Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput., 28(4):1298–1309, 1999. [doi:10.1137/S0097539796309764]

[29]    George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher: An analysis of approximations for maximizing submodular set functions—-I. Math. Programming, 14(1):265–294, 1978. [doi:10.1007/BF01588971]

[30]   Fred van Nijnatten, René Sitters, Gerhard J. Woeginger, Alexander Wolff, and Mark de Berg: The traveling salesman problem under squared Euclidean distances. In Proc. 27th Symp. Theoret. Aspects of Comp. Sci. (STACS’10), pp. 239–250. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2010. [doi:10.4230/LIPIcs.STACS.2010.2458, arXiv:1001.0236]

[31]   Yuval Rabani and Gabriel Scalosub: Bicriteria approximation tradeoff for the node-cost budget problem. ACM Trans. Algorithms, 5(2):19:1–14, 2009. Preliminary version in SWAT’08. [doi:10.1145/1497290.1497295]

[32]   Fabio Vandin, Eli Upfal, and Benjamin J. Raphael: Algorithms for detecting significantly mutated pathways in cancer. J. Comput. Biology, 18(3):507–522, 2011. Preliminary version in RECOMB’10. [doi:10.1089/cmb.2010.0265]

[33]   Laurence A. Wolsey: Maximising real-valued submodular functions: primal and dual heuristics for location problems. Math. Oper. Res., 7(3):410–425, 1982. [doi:10.1287/moor.7.3.410]