Timothy M. Chan's Publications: Approximation algorithms for NP-hard geometric problems


Stabbing rectangles by line segments: How decomposition reduces the shallow-cell complexity

(with
Thomas C. van Dijk, Krzysztof Fleszar, Joachim Spoerhase, and Alexander Wolff)

We initiate the study of the following natural geometric optimization problem. The input is a set of axis-aligned rectangles in the plane. The objective is to find a set of horizontal line segments of minimum total length so that every rectangle is stabbed by some line segment. A line segment stabs a rectangle if it intersects its left and its right boundary. The problem, which we call Stabbing, can be motivated by a resource allocation problem and has applications in geometric network design. To the best of our knowledge, only special cases of this problem have been considered so far.

Stabbing is a weighted geometric set cover problem, which we show to be NP-hard. A constrained variant of Stabbing turns out to be even APX-hard. While for general set cover the best possible approximation ratio is Theta(log n), it is an important field in geometric approximation algorithms to obtain better ratios for geometric set cover problems. Chan et al. [SODA'12] generalize earlier results by Varadarajan [STOC'10] to obtain sub-logarithmic performances for a broad class of weighted geometric set cover instances that are characterized by having low shallow-cell complexity. The shallow-cell complexity of Stabbing instances, however, can be high so that a direct application of the framework of Chan et al. gives only logarithmic bounds. We still achieve a constant-factor approximation by decomposing general instances into what we call laminar instances that have low enough complexity.

Our decomposition technique yields constant-factor approximations also for the variant where rectangles can be stabbed by horizontal and vertical segments and for two further geometric set cover problems.


Minimum length embedding of planar graphs at fixed vertex locations

(with Hella-Franziska Hoffmann, Stephen Kiazyk, and
Anna Lubiw)

We consider the problem of finding a planar embedding of a graph at fixed vertex locations that minimizes the total edge length. The problem is known to be NP-hard. We give polynomial time algorithms achieving an O(n^{1/2} log n) approximation for paths and matchings, and an O(n) approximation for general graphs.


Geometric red-blue set cover for unit squares and related problems

(with Nan Hu)

We study a geometric version of the Red-Blue Set Cover problem originally proposed by Carr, Doddi, Konjevod, and Marathe (SODA 2000): given a red point set, a blue point set, and a set of objects, we want to use objects to cover all the blue points, while minimizing the number of red points covered. We prove that the problem is NP-hard even when the objects are unit squares in 2D, and we give the first PTAS for this case. The technique we use simplifies and unifies previous PTASes for the weighted geometric set cover problem and the unique maximum coverage problem for 2D unit squares.


Smart-grid electricity allocation via strip packing with slicing

(with Soroush Alamdari,
Therese Biedl, Elyot Grant, Krishnam Raju Jampani, S. Keshav, Anna Lubiw, and Vinayak Pathak)

One advantage of smart grids is that they can reduce the peak load by distributing electricity-demands over multiple short intervals. Finding a schedule that minimizes the peak load corresponds to a variant of a strip packing problem. Normally, for strip packing problems, a given set of axis-aligned rectangles must be packed into a fixed-width strip, and the goal is to minimize the height of the strip. The electricity-allocation application can be modelled as strip packing with slicing: each rectangle may be cut vertically into multiple slices and the slices may be packed into the strip as individual pieces. The stacking constraint forbids solutions in which a vertical line intersects two slices of the same rectangle.

We give a fully polynomial time approximation scheme for this problem, as well as a practical polynomial time algorithm that slices each rectangle at most once and yields a solution of height at most 5/3 times the optimal height.


Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set

In the conflict-free coloring problem, for a given range space, we want to bound the minimum value F(n) such that every set P of n points can be colored with F(n) colors with the property that every nonempty range contains a unique color. We prove a new upper bound O(n^{0.368}) with respect to orthogonal ranges in two dimensions (i.e., axis-parallel rectangles), which is the first improvement over the previous bound O(n^{0.382}) by Ajwani, Elbassioni, Govindarajan, and Ray [SPAA'07]. This result leads to an O(n^{1-0.632/2^{d-2}}) upper bound with respect to orthogonal ranges (boxes) in dimension d, and also an O(n^{1-0.632/(2^{d-3}-0.368)}) upper bound with respect to dominance ranges (orthants) in dimension d >= 4.

We also observe that combinatorial results on conflict-free coloring can be applied to the analysis of approximation algorithms for discrete versions of geometric independent set problems. Here, given a set P of (weighted) points and a set S of ranges, we want to select the largest(-weight) subset Q of P with the property that every range of S contains at most one point of Q. We obtain, for example, a randomized O(n^{0.368})-approximation algorithm for this problem with respect to orthogonal ranges in the plane.


Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling

(with Elyot Grant,
Jochen Koenemann, and Malcolm Sharpe)

The minimum-weight set cover problem is widely known to be O(log n)-approximable, with no improvement possible in the general case. We take the approach of exploiting problem structure to achieve better results, by providing a geometry-inspired algorithm whose approximation guarantee depends solely on an instance-specific combinatorial property known as shallow cell complexity (SCC). Roughly speaking, a set cover instance has low SCC if any column-induced submatrix of the corresponding element-set incidence matrix has few distinct rows. By adapting and improving Varadarajan's recent quasi-uniform random sampling method for weighted geometric covering problems, we obtain strong approximation algorithms for a structurally rich class of weighted covering problems with low SCC.

Our main result has several immediate consequences. Among them, we settle an open question of Chakrabarty et al. by showing that weighted instances of the capacitated covering problem with underlying network structure have O(1)-approximations. Additionally, our improvements to Varadarajan's sampling framework yield several new results for weighted geometric set cover, hitting set, and dominating set problems. In particular, for weighted covering problems exhibiting linear (or near-linear) union complexity, we obtain approximability results agreeing with those known for the unweighted case. For example, we obtain a constant approximation for the weighted disk cover problem, improving upon the 2^{O(log* n)}-approximation known prior to our work and matching the O(1)-approximation known for the unweighted variant. We also obtain an O(log log* n)-approximation for weighted fat triangle cover.


Exact algorithms and APX-hardness results for geometric set cover

(with Elyot Grant)

We study several geometric set cover problems in which the goal is to compute a minimum cover of a given set of points in Euclidean space by a family of geometric objects. We give a short proof that this problem is APX-hard when the objects are axis-aligned fat rectangles, even when each rectangle is an epsilon-perturbed copy of a single unit square. We extend this result to several other classes of objects including almost-circular ellipses, axis-aligned slabs, downward shadows of line segments, downward shadows of graphs of cubic functions, 3-dimensional unit balls, and axis-aligned cubes, as well as some related hitting set problems. Our hardness results are all proven by encoding a highly structured minimum vertex cover problem which we believe may be of independent interest.

In contrast, we give a polynomial-time dynamic programming algorithm for 2-dimensional set cover where the objects are pseudodisks containing the origin or are downward shadows of pairwise 2-intersecting x-monotone curves. Our algorithm extends to the weighted case where a minimum-cost cover is required.


Stochastic minimum spanning trees in Euclidean spaces

(with
Pegah Kamousi and Subhash Suri)

We study the complexity of geometric minimum spanning trees under a stochastic model of input: Suppose we are given a master set of points {s_1,s_2,...,s_n} in d-dimensional Euclidean space, where each point s_i is active with some independent and arbitrary but known probability p_i. We want to compute the expected length of the minimum spanning tree (MST) of the active points. This particular form of stochastic problems has not been investigated before in computational geometry to our knowledge, and is motivated by uncertainty inherent in many sources of geometric data.

  1. We show that this stochastic MST problem is #P-hard for any dimension d >= 2.
  2. We present a simple fully polynomial randomized approximation scheme (FPRAS) in any metric, and thus also in any Euclidean, space.
  3. For d=2, we present two deterministic approximation algorithms: an O(n^4)-time constant-factor algorithm, and a PTAS based on a combination of shifted quadtrees and dynamic programming.
  4. Finally, for the related problem of approximating the tail bounds of the distribution of the MST length, we observe that no polynomial algorithm with any multiplicative factor is possible for d >= 2, assuming P != NP.
In addition to this existential model of stochastic input, we also briefly consider a locational model where each point is present with certainty but its location is probabilistic.


Approximation algorithms for maximum independent set of pseudo-disks

(with
Sariel Har-Peled)

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, that 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.


Approximating the piercing number for unit-height rectangles

(with Abdullah-Al Mahmood)

The piercing problem seeks the minimum number of points for a set of objects such that each object contains at least one of the points. We present a polynomial-time approximation scheme (PTAS) for the piercing problem for a set of axis-parallel unit-height rectangles. We also examine the problem in a dynamic setting and show how to maintain a factor-2 approximation under insertions in logarithmic amortized time, by solving an incremental version of the maximum independent set problem for interval graphs.


Approximation algorithms for maximum cliques in 3D unit-disk graphs

(with
Peyman Afshani)

We study two problems for a given n-point set in 3-space: finding a largest subset with diameter at most one, and finding a subset of k points with minimum diameter. For the former problem we suggest several polynomial-time algorithms with constant approximation factors, the best of which has factor pi / arccos(1/3) < 2.553. For the latter problem we observe that there is a polynomial-time approximation scheme.


A note on maximum independent sets in rectangle intersection graphs

Finding the maximum independent set in the intersection graph of n axis-parallel rectangles is NP-hard. We re-examine two known approximation results for this problem. For the case of rectangles of unit height, Agarwal, van Kreveld, and Suri (1997) gave a (1+1/k)-factor algorithm with an O(n log n + n^{2k-1}) time bound for any integer constant k >= 1; we describe a similar algorithm running in only O(n log n + nD^{k-1}) time, where D <= n denotes the maximum number of rectangles a point can be in. For the general case, Berman, DasGupta, Muthukrishnan, and Ramaswami (2001) gave a log_k n-factor algorithm with an O(n^{k+1}) time bound for any integer constant k >= 2; we describe similar algorithms running in O(n log n + nD^{k-2}) and n^{O(k/log k)} time.


Euclidean bounded-degree spanning tree ratios

Let tau_K be the worst-case (supremum) ratio of the weight of the minimum degree-K spanning tree to the weight of the minimum spanning tree, over all finite point sets in the Euclidean plane. It is known that tau_2 = 2 and tau_5 = 1. In STOC'94, Khuller, Raghavachari, and Young established the following inequalities: 1.103 < tau_3 <= 1.5 and 1.035 < tau_4 <= 1.25. We present the first improved upper bounds: tau_3 < 1.402 and tau_4 < 1.143. As a result, we obtain better approximation algorithms for Euclidean minimum bounded-degree spanning trees.

Let tau_K^{(d)} be the analogous ratio in d-dimensional space. Khuller et al. showed that tau_3^{(d)} < 1.667 for any d. We observe that tau_3^{(d)} < 1.633.


Polynomial-time approximation schemes for packing and piercing fat objects

We consider two problems: given a collection of n fat objects in a fixed dimension, Recently, Erlebach, Jansen, and Seidel gave a polynomial-time approximation scheme (PTAS) for the packing problem, based on a shifted hierarchical subdivision method. Using shifted quadtrees, we describe a similar algorithm for packing but with a smaller time bound. Erlebach et al.'s algorithm requires polynomial space. We describe a different algorithm, based on geometric separators, that requires only linear space. This algorithm can also be applied to piercing, yielding the first PTAS for that problem.


Copyright Notice

The documents contained in this directory are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.


Timothy Chan (Last updated September 2018)