Packing and Covering problems with geometric regions in the plane have been extensively studied and several notions of "complexity" of the regions involved have been developed and exploited to obtain good approximation algorithms. Examples of such complexity measures are VC-dimension, union complexity, shallow-cell complexity, fatness, etc. While these restrictions lead to constant-factor approximation algorithms in many cases, they typically do not lead to PTASs. In fact, several geometric Set Cover and Discrete Independent Set variants remain APX-hard even when these parameters are small, as demonstrated in earlier work by Chan and Grant (Exact algorithms and APX-hardness results for geometric packing and covering problems. Comput. Geom., 2014), and by Har-Peled and Quanrud (Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs. SIAM J. Comput., 2017). A key feature of these hardness constructions is that many pairs of regions in the input pierce one another. Motivated by this observation, we initiate a systematic study of geometric families parameterized by their piercing complexity. A connected region A is said to pierce a connected region B if B ⧵ A has more than one connected component; we consider instances in which every region is pierced by at most a constant number of others. This framework smoothly interpolates between the classical non-piercing case-where local-search PTASs are known due to Raman and Ray (Constructing Planar Support for Non-Piercing Regions, Discret. Comput. Geom., 2020), and the fully general case, where APX-hardness persists. Our main contribution is to show that bounded-piercing families admit efficient approximation schemes for fundamental geometric optimization problems. For regions in the plane with a constant piercing bound, we obtain PTASs for the (unweighted) Discrete Independent Set and Set Cover problems, and constant-factor approximation algorithms for their weighted variants. These results strictly generalize the known PTASs for non-piercing families and yield improved guarantees for several long-standing special cases, including Independent Set and Set Cover with axis-parallel rectangles under bounded piercing. Overall, our work identifies piercing complexity as a robust and expressive topological parameter-distinct from geometric notions such as density or fatness-and demonstrates that bounding this parameter yields a broad family of geometric instances for which PTASs become achievable.

Let $Γ$ be an arrangement of Jordan curves in the plane, i.e., simple closed curves in the plane. For any curve $γ\in Γ$, we denote the bounded region enclosed by $γ$ as $\tildeγ$. We say that $Γ$ is non-piercing if for any two curves $α, β\in Γ$, $\tildeα \,\setminus\, \tildeβ$ is connected. A non-piercing arrangement of curves generalizes a set of $2$-intersecting curves in which each pair of curves intersect in at most two points. Snoeyink and Hershberger (``Sweeping Arrangements of Curves'', SoCG '89) proved that if we are given an arrangement $Γ$ of $2$-intersecting curves and a {\em sweep} curve $γ\inΓ$, then the arrangement can be \emph{swept} by $γ$ while always maintaining the $2$-intersecting property of the curves in $Γ$. We generalize the result of Snoeyink and Hershberger to the setting of non-piercing arrangements. Given an arrangement $Γ$ of non-piercing curves, a sweep curve $γ\in Γ$, and a point $P$ in $\tildeγ$, we show that we can continuously shrink $γ$ to $P$ so that throughout the process, the arrangement remains non-piercing (except at a finite set of points in time where $γ$ crosses other curves), and $P$ lies in $\tildeγ$. We show that our arguments can be modified if $P$ lies outside $\tildeγ$, and we want to sweep $γ$ \emph{outwards} so that $P$ lies outside $\tildeγ$, and the arrangement remains non-piercing. As a second contribution, we give an alternate proof of the result of Snoeyink and Hershberger, and give several applications of our results to combinatorial and algorithmic questions including to the \emph{multi-hitting set} problem involving points and non-piercing regions.

For a hypergraph ℋ = (X,ℰ) a support is a graph G on X such that for each E ∈ ℰ, the induced subgraph of G on the elements in E is connected. If G is planar, we call it a planar support. A set of axis parallel rectangles ℛ forms a non-piercing family if for any R₁, R₂ ∈ ℛ, R₁⧵R₂ is connected. Given a set P of n points in ℝ² and a set ℛ of m non-piercing axis-aligned rectangles, we give an algorithm for computing a planar support for the hypergraph (P,ℛ) in O(nlog² n + (n+m)log m) time, where each R ∈ ℛ defines a hyperedge consisting of all points of P contained in R.

We study the priority set cover problem for simple geometric set systems in the plane. For pseudo-halfspaces in the plane we obtain a PTAS via local search by showing that the corresponding set system admits a planar support. We show that the problem is APX-hard even for unit disks in the plane and argue that in this case the standard local search algorithm can output a solution that is arbitrarily bad compared to the optimal solution. We then present an LP-relative constant factor approximation algorithm (which also works in the weighted setting) for unit disks via quasi-uniform sampling. As a consequence we obtain a constant factor approximation for the capacitated set cover problem with unit disks. For arbitrary size disks, we show that the problem is at least as hard as the vertex cover problem in general graphs even when the disks have nearly equal sizes. We also present a few simple results for unit squares and orthants in the plane.

In the Set Multicover problem, we are given a set system (X,𝒮), where X is a finite ground set, and 𝒮 is a collection of subsets of X. Each element x ∈ X has a non-negative demand d(x). The goal is to pick a smallest cardinality sub-collection 𝒮' of 𝒮 such that each point is covered by at least d(x) sets from 𝒮'. In this paper, we study the set multicover problem for set systems defined by points and non-piercing regions in the plane, which includes disks, pseudodisks, k-admissible regions, squares, unit height rectangles, homothets of convex sets, upward paths on a tree, etc. We give a polynomial time (2+ε)-approximation algorithm for the set multicover problem (P, ℛ), where P is a set of points with demands, and ℛ is a set of non-piercing regions, as well as for the set multicover problem (𝒟, P), where 𝒟 is a set of pseudodisks with demands, and P is a set of points in the plane, which is the hitting set problem with demands.

Given a hypergraph H=(X,S), a planar support for H is a planar graph G with vertex set X, such that for each hyperedge S in S, the sub-graph of G induced by the vertices in S is connected. Planar supports for hypergraphs have found several algorithmic applications, including several packing and covering problems, hypergraph coloring, and in hypergraph visualization. The main result proved in this paper is the following: given two families of regions R and B in the plane, each of which consists of connected, non-piercing regions, the intersection hypergraph H_R(B) = (B, {B_r}_{r in R}), where B_r = {b in B: b cap r != empty set} has a planar support. Further, such a planar support can be computed in time polynomial in |R|, |B|, and the number of vertices in the arrangement of the regions in R cup B. Special cases of this result include the setting where either the family R, or the family B is a set of points. Our result unifies and generalizes several previous results on planar supports, PTASs for packing and covering problems on non-piercing regions in the plane and coloring of intersection hypergraph of non-piercing regions.

In this paper, we design the first polynomial time approximation schemes for the Set Cover and Dominating Set problems when the underlying sets are non-piercing regions (which include pseudodisks). We show that the local search algorithm that yields PTASs when the regions are disks [Aschner/Katz/Morgenstern/Yuditsky, WALCOM 2013; Gibson/Pirwani, 2005; Mustafa/Raman/Ray, 2015] can be extended to work for non-piercing regions. While such an extension is intuitive and natural, attempts to settle this question have failed even for pseudodisks. The techniques used for analysis when the regions are disks rely heavily on the underlying geometry, and do not extend to topologically defined settings such as pseudodisks. In order to prove our results, we introduce novel techniques that we believe will find applications in other problems. We then consider the Capacitated Region Packing problem. Here, the input consists of a set of points with capacities, and a set of regions. The objective is to pick a maximum cardinality subset of regions so that no point is covered by more regions than its capacity. We show that this problem admits a PTAS when the regions are k-admissible regions (pseudodisks are 2-admissible), and the capacities are bounded. Our result settles a conjecture of Har-Peled (see Conclusion of [Har-Peled, SoCG 2014]) in the affirmative. The conjecture was for a weaker version of the problem, namely when the regions are pseudodisks, the capacities are uniform, and the point set consists of all points in the plane. Finally, we consider the Capacitated Point Packing problem. In this setting, the regions have capacities, and our objective is to find a maximum cardinality subset of points such that no region has more points than its capacity. We show that this problem admits a PTAS when the capacity is unity, extending one of the results of Ene et al. [Ene/Har-Peled/Raichel, SoCG 2012].

Weighted geometric set-cover problems arise naturally in several geometric and nongeometric settings (e.g., the breakthrough of Bansal and Pruhs [Proceedings of FOCS, 2010, pp. 407--414] reduces a wide class of machine scheduling problems to weighted geometric set cover). More than two decades of research has succeeded in settling the $(1+\epsilon)$-approximability status for most geometric set-cover problems, except for some basic scenarios which are still lacking. One is that of weighted disks in the plane for which, after a series of papers, Varadarajan [Proceedings of STOC'10, 2010, pp. 641--648] presented a clever quasi-sampling technique, which together with improvements by Chan et al. [Proceedings of SODA, 2012, pp. 1576--1585], yielded an $O(1)$-approximation algorithm. Even for the unweighted case, a polynomial time approximation scheme (PTAS) for a fundamental class of objects called pseudodisks (which includes halfspaces, disks, unit-height rectangles, translates of convex sets, etc.) is currently unknown. Another fundamental case is weighted halfspaces in $\mathfrak{R}^3$, for which a PTAS is currently lacking. In this paper, we present a quasi PTAS (QPTAS) for all these remaining problems. Our results are based on the separator framework of Adamaszek and Wiese [Proceedings of FOCS, 2013, pp. 400--409; Proceedings of SODA, 2014, pp. 645--656], who recently obtained a QPTAS for a weighted independent set of polygonal regions. This rules out the possibility that these problems are APX-hard, assuming ${NP} \not\subseteq {DTIME}(2^{polylog(n)})$. Together with the recent work of Chan and Grant [Comput. Geom., 47 (2014), pp. 112--124], this settles the APX-hardness status for all natural geometric set-cover problems.

Weighted geometric set-cover problems arise naturally in several geometric and non-geometric settings (e.g. the breakthrough of Bansal and Pruhs (FOCS 2010) reduces a wide class of machine scheduling problems to weighted geometric set-cover). More than two decades of research has succeeded in settling the (1+∈)-approximability status for most geometric set-cover problems, except for four basic scenarios which are still lacking. One is that of weighted disks in the plane for which, after a series of papers, Varadarajan (STOC 2010) presented a clever quasi-sampling technique, which together with improvements by Chan et al(SODA 2012), yielded a O(1)-approximation algorithm. Even for the unweighted case, a PTAS for a fundamental class of objects called pseudodisks (which includes disks, unit-height rectangles, translates of convex sets etc.) is currently unknown. Another fundamental case is weighted halfspaces in R3, for which a PTAS is currently lacking. In this paper, we present a QPTAS for all of these remaining problems. Our results are based on the separator framework of Adamaszek and Wiese (FOCS 2013, SODA 2014), who recently obtained a QPTAS for weighted independent set of polygonal regions. This rules out the possibility that these problems are APX-hard, assuming NP DTIME(2polylog(n)). Together with the recent work of Chan-Grant (CGTA 2014), this settles the APX-hardness status for all natural geometric set-cover problems.

Given a graph G = ( V, E ) and positive integral vertex weights w : V → N , the max-coloring problem seeks to find a proper vertex coloring of G whose color classes C 1 , C 2 , …, C k , minimize ∑ i =1 k max v ∈ C i w ( v ). This problem, restricted to interval graphs, arises whenever there is a need to design dedicated memory managers that provide better performance than the general-purpose memory management of the operating system. Though this problem seems similar to the dynamic storage allocation problem, there are fundamental differences. We make a connection between max-coloring and online graph coloring and use this to devise a simple 2-approximation algorithm for max-coloring on interval graphs. We also show that a simple first-fit strategy, that is a natural choice for this problem, yields an 8-approximation algorithm. We show this result by proving that the first-fit algorithm for online coloring an interval graph G uses no more than 8 ċ χ( G ) colors, significantly improving the bound of 26 ċ χ( G ) by Kierstead and Qin [1995]. We also show that the max-coloring problem is NP-hard. The problem of online coloring of intervals with bandwidths is a simultaneous generalization of online interval coloring and online bin packing. The input is a set I of intervals, each interval i ∈ I having an associated bandwidth b ( i ) ∈ (0, 1]. We seek an online algorithm that produces a coloring of the intervals such that for any color c and any real r , the sum of the bandwidths of intervals containing r and colored c is at most 1. Motivated by resource allocation problems, Adamy and Erlebach [2003] consider this problem and present an algorithm that uses at most 195 times the number of colors used by an optimal offline algorithm. Using the new analysis of first-fit coloring of interval graphs, we show that the Adamy-Erlebach algorithm is 35-competitive. Finally, we generalize the Adamy-Erlebach algorithm to a class of algorithms and show that a different instance from this class is 30-competitive.

The Lovaacutesz thetav-function [Lov79] on a graph G = (V,E) can be defined as the maximum of the sum of the entries of a positive semidefinite matrix X, whose trace Tr(X) equals 1, and Xij= 0 whenever {i, j} isin E. This function appears as a subroutine for many algorithms for graph problems such as maximum independent set and maximum clique. We apply Arora and Kale's primal-dual method for SDP to design an approximate algorithm for the thetav-function with an additive error of delta > 0, which runs in time O(alpha2n2/delta2log n middot Me), where alpha = thetav(G) and Me= O(n3) is the time for a matrix exponentiation operation. Moreover, our techniques generalize to the weighted Lovasz thetav-function, and both the maximum independent set weight and the maximum clique weight for vertex weighted perfect graphs can be approximated within a factor of (1+epsi) in time O(epsi-2n5log n).

Given a system of constraints , where ai ∊ {0, 1}n, and ℓi, ui ∊ ℝ+, for i = 1, …, m, we consider the problem Mrfs of finding the largest subsystem for which there exists a feasible solution x ≥ 0. We present approximation algorithms and inapproximability results for this problem, and study some important special cases. Our main contributions are: 1. In the general case, where ai ∊ {0, 1}n, a sharp separation in the approximability between the case when L = max{ℓ1, ⃛, ℓm} is bounded above by a polynomial in n and m, and the case when it is not. 2. In the case where A is an interval matrix, a sharp separation in approximability between the case where we allow a violation of the upper bounds by at most a (1 + ∊) factor, for any fixed ∊ > 0 and the case where no violations are allowed. Along the way, we prove that the induced matching problem on bipartite graphs is inapproximable beyond a factor of , for any ∊ > 0 unless NP=ZPP. Finally, we also show applications of Mrfs to some recently studied pricing problems.