×

Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. (English) Zbl 1422.68253

Bansal, Nikhil (ed.) et al., Algorithms – ESA 2015. 23rd annual European symposium, Patras, Greece, September 14–16, 2015. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 9294, 865-877 (2015).
Summary: We study a general family of facility location problems defined on planar graphs and on the 2-dimensional plane. In these problems, a subset of \(k\) objects has to be selected, satisfying certain packing (disjointness) and covering constraints. Our main result is showing that, for each of these problems, the \(n^{{\mathcal{O}}(k)}\) time brute force algorithm of selecting \(k\) objects can be improved to \(n^{{\mathcal{O}}(\sqrt{k})}\) time. The algorithm is based on focusing on the Voronoi diagram of a hypothetical solution of \(k\) objects; this idea was introduced recently in the design of geometric QPTASs, but was not yet used for exact algorithms and for planar graphs. As concrete consequences of our main result, we obtain \(n^{{\mathcal{O}}(\sqrt{k})}\) time algorithms for the following problems: \(d\)-Scattered Set in planar graphs (find \(k\) vertices at pairwise distance \(d\)); \(d\)-Dominating Set/\((k,d)\)-Center in planar graphs (find \(k\) vertices such that every vertex is at distance at most \(d\) from these vertices); select \(k\) pairwise disjoint connected vertex sets from a given collection; select \(k\) pairwise disjoint disks in the plane (of possibly different radii) from a given collection; cover a set of points in the plane by selecting \(k\) disks/axis-parallel squares from a given collection. We complement these positive results with lower bounds suggesting that some similar, but slightly more general problems (such as covering points with axis-parallel rectangles) do not admit \(n^{{\mathcal{O}}(\sqrt{k})}\) time algorithms.
For the entire collection see [Zbl 1320.68011].

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
90B80 Discrete location and assignment
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adamaszek, A., Wiese, A.: Approximation schemes for maximum weight independent set of rectangles. In: FOCS, pp. 400–409 (2013) · doi:10.1109/FOCS.2013.50
[2] Adamaszek, A., Wiese, A.: A QPTAS for maximum weight independent set of polygons with polylogarithmically many vertices. In: SODA, pp. 645–656 (2014) · doi:10.1137/1.9781611973402.49
[3] Agarwal, P.K., Overmars, M.H., Sharir, M.: Computing maximally separated sets in the plane. SIAM J. Comput. 36(3), 815–834 (2006) · Zbl 1120.68102 · doi:10.1137/S0097539704446591
[4] Alber, J., Fiala, J.: Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. J. Algorithms 52(2), 134–151 (2004) · Zbl 1100.68074 · doi:10.1016/j.jalgor.2003.10.001
[5] Chitnis, R.H., Hajiaghayi, M., Marx, D.: Tight bounds for Planar Strongly Connected Steiner Subgraph with fixed number of terminals (and extensions). In: SODA, pp. 1782–1801 (2014)
[6] Demaine, E.D., Hajiaghayi, M.: The bidimensionality theory and its algorithmic applications. Comput. J. 51(3), 292–302 (2008) · Zbl 05534222 · doi:10.1093/comjnl/bxm033
[7] Har-Peled, S.: Quasi-polynomial time approximation scheme for sparse subsets of polygons. In: SoCG, pp. 120 (2014) · Zbl 1395.68306 · doi:10.1145/2582112.2582157
[8] Hwang, R.Z., Lee, R.C.T., Chang, R.C.: The slab dividing approach to solve the Euclidean p-center problem. Algorithmica 9(1), 1–22 (1993) · Zbl 0766.68136 · doi:10.1007/BF01185335
[9] Klein, P.N., Marx, D.: Solving Planar k -Terminal Cut in \(O(n^{c \sqrt{k}})\) Time. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol. 7391, pp. 569–580. Springer, Heidelberg (2012) · Zbl 1272.68157 · doi:10.1007/978-3-642-31594-7_48
[10] Klein, P.N., Marx, D.: A subexponential parameterized algorithm for Subset TSP on planar graphs. In: SODA, pp. 1812–1830 (2014) · doi:10.1137/1.9781611973402.131
[11] Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. CoRR, abs/1504.05476 (2015) · Zbl 1422.68253
[12] Marx, D., Sidiropoulos, A.: The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric problems. In: SoCG, p. 67 (2014) · Zbl 1395.68309
[13] Mustafa, N.H., Raman, R., Ray, S.: QPTAS for geometric set-cover problems via optimal separators. CoRR, abs/1403.0835 (2014)
[14] Pilipczuk, M., Pilipczuk, M., Sankowski, P., van Leeuwen, E.J.: Network sparsification for Steiner problems on planar and bounded-genus graphs. In: FOCS, pp. 276–285. IEEE Computer Society (2014) · doi:10.1109/FOCS.2014.37
[15] Pătraşcu, M., Williams, R.: On the possibility of faster SAT algorithms. In: SODA, pp. 1065–1075 (2010) · Zbl 1288.68135
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.