Abstract. Geometric set cover is a classical problem in computational geometry, which has been extensively studied in the past. In the dynamic version of the problem, points and ranges may be inserted and deleted, and our goal is to efficiently maintain a set cover solution (satisfying certain quality requirements) for the dynamic problem instance. In this paper, we give a plethora of new dynamic geometric set cover data structures in one and two dimensions, which significantly improve and extend the previous results. Our results include the following: (1) The first data structure for [Formula: see text]-approximate dynamic interval set cover with polylogarithmic amortized update time. Specifically, we achieve an update time of [Formula: see text], improving the [Formula: see text] bound of Agarwal et al. [ Proceedings of the 36 th Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 164, Schloss Dagstuhl - Leibniz Center for Informatics, 2020, 27; ACM Trans. Algorithms, 18 (2022), 40], where [Formula: see text] denotes an arbitrarily small constant. (2) A data structure for [Formula: see text]-approximate dynamic unit-square set cover with [Formula: see text] amortized update time, substantially improving the [Formula: see text] update time of Agarwal et al. (3) A data structure for [Formula: see text]-approximate dynamic square set cover with [Formula: see text] randomized amortized update time, improving the [Formula: see text] update time of Chan and He [ Proceedings of the 36 th Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 164, Schloss Dagstuhl - Leibniz Center for Informatics, 2020; J. Comput. Geom., 13 (2022), pp. 90–114]. (4) A data structure for [Formula: see text]-approximate dynamic two-dimensional half-plane set cover with [Formula: see text] randomized amortized update time. The previous solution for a half-plane set cover by Chan and He [ Proceedings of the 37 th International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform. 189, Schloss Dagstuhl - Leibniz Center for Informatics, 2021, 25; J. Comput. Geom., 13 (2022), pp. 90–114] is slower and can only report the size of the approximate solution. (5) The first sublinear results for the weighted version of dynamic geometric set cover. Specifically, we give a data structure for [Formula: see text]-approximate dynamic weighted interval set cover with [Formula: see text] amortized update time and a data structure for [Formula: see text]-approximate dynamic weighted unit-square set cover with [Formula: see text] amortized update time.

Let $X$ be a set of points in $\mathbb{R}^2$ and $\mathcal{O}$ be a set of geometric objects in $\mathbb{R}^2$, where $|X| + |\mathcal{O}| = n$. We study the problem of computing a minimum subset $\mathcal{O}^* \subseteq \mathcal{O}$ that encloses all points in $X$. Here a point $x \in X$ is enclosed by $\mathcal{O}^*$ if it lies in a bounded connected component of $\mathbb{R}^2 \backslash (\bigcup_{O \in \mathcal{O}^*} O)$. We propose two algorithmic frameworks to design polynomial-time approximation algorithms for the problem. The first framework is based on sparsification and min-cut, which results in $O(1)$-approximation algorithms for unit disks, unit squares, etc. The second framework is based on LP rounding, which results in an $O(α(n)\log n)$-approximation algorithm for segments, where $α(n)$ is the inverse Ackermann function, and an $O(\log n)$-approximation algorithm for disks.

Despite numerous results about the list decoding of Hamming-metric codes, development of list decoding on rank-metric codes is not as rapid as its counterpart. The bound of list decoding obeys the Gilbert-Varshamov bound in both the metrics. In the case of the Hamming-metric, the Gilbert-Varshamov bound is a trade-off among rate, decoding radius and alphabet size, while in the case of the rank-metric, the Gilbert-Varshamov bound is a trade-off among rate, decoding radius and column-to-row ratio (i.e., the ratio between the numbers of columns and rows). Hence, alphabet size and column-to-row ratio play a similar role for list decodability in each metric. In the case of the Hamming-metric, it is more challenging to list decode codes over smaller alphabets. In contrast, in the case of the rank-metric, it is more difficult to list decode codes with large column-to-row ratio. In particular, it is extremely difficult to list decode square matrix rank-metric codes (i.e., the column-to-row ratio is equal to 1). The main purpose of this paper is to explicitly construct a class of rank-metric codes 𝒞 of rate R with the column-to-row ratio up to 2/3 and efficiently list decode these codes with decoding radius beyond the decoding radius (1-R)/2 (note that (1-R)/2 is at least half of relative minimum distance δ). In literature, the largest column-to-row ratio of rank-metric codes that can be efficiently list decoded beyond half of minimum distance is 1/2. Thus, it is greatly desired to efficiently design list decoding algorithms for rank-metric codes with the column-to-row ratio bigger than 1/2 or even close to 1. Our key idea is to compress an element of the field F_qⁿ into a smaller F_q-subspace via a linearized polynomial. Thus, the column-to-row ratio gets increased at the price of reducing the code rate. Our result shows that the compression technique is powerful and it has not been employed in the topic of list decoding of both the Hamming and rank metrics. Apart from the above algebraic technique, we follow some standard techniques to prune down the list. The algebraic idea enables us to pin down the message into a structured subspace of dimension linear in the number n of columns. This "periodic" structure allows us to pre-encode the message to prune down the list.

Geometric set cover is a classical problem in computational geometry, which has been extensively studied in the past. In the dynamic version of the problem, points and ranges may be inserted and deleted, and our goal is to efficiently maintain a set cover solution (satisfying certain quality requirement) for the dynamic problem instance. In this paper, we give a plethora of new dynamic geometric set cover data structures in 1D and 2D, which significantly improve and extend the previous results. Our results include the following: The first data structure for (1 + ∊)-approximate dynamic interval set cover with polylogarithmic amortized update time. Specifically, we achieve an update time of O(log3 n/∊), improving the O(nδ/∊) bound of Agarwal et al. [SoCG'20], where δ > 0 denotes an arbitrarily small constant. A data structure for O(1)-approximate dynamic unit-square set cover with amortized update time, substantially improving the O(n1/2+δ) update time of Agarwal et al. [SoCG'20]. A data structure for O(1)-approximate dynamic square set cover with O(n1/2+δ) randomized amortized update time, improving the O(n2/3+δ) update time of Chan and He [SoCG'21]. A data structure for O(1)-approximate dynamic 2D halfplane set cover with O(n17/23+δ) randomized amortized update time. The previous solution for halfplane set cover by Chan and He [SoCG'21] is slower and can only report the size of the approximate solution. The first sublinear results for the weighted version of dynamic geometric set cover. Specifically, we give a data structure for (3 + o(1))-approximate dynamic weighted interval set cover with amortized update time and a data structure for O(1)-approximate dynamic weighted unit-square set cover with O(nδ) amortized update time.

We study geometric set cover problems in dynamic settings, allowing insertions and deletions of points and objects. We present the first dynamic data structure that can maintain an $O(1)$-approximation in sublinear update time for set cover for axis-aligned squares in 2D. More precisely, we obtain randomized update time $O(n^{2/3+δ})$ for an arbitrarily small constant $δ>0$. Previously, a dynamic geometric set cover data structure with sublinear update time was known only for unit squares by Agarwal, Chang, Suri, Xiao, and Xue [SoCG 2020]. If only an approximate size of the solution is needed, then we can also obtain sublinear amortized update time for disks in 2D and halfspaces in 3D. As a byproduct, our techniques for dynamic set cover also yield an optimal randomized $O(n\log n)$-time algorithm for static set cover for 2D disks and 3D halfspaces, improving our earlier $O(n\log n(\log\log n)^{O(1)})$ result [SoCG 2020].

We improve the running times of O(1)-approximation algorithms for the set cover problem in geometric settings, specifically, covering points by disks in the plane, or covering points by halfspaces in three dimensions. In the unweighted case, Agarwal and Pan [SoCG 2014] gave a randomized O(n log⁴n)-time, O(1)-approximation algorithm, by using variants of the multiplicative weight update (MWU) method combined with geometric data structures. We simplify the data structure requirement in one of their methods and obtain a deterministic O(n log³n log log n)-time algorithm. With further new ideas, we obtain a still faster randomized O(n log n(log log n)^O(1))-time algorithm. For the weighted problem, we also give a randomized O(n log⁴n log log n)-time, O(1)-approximation algorithm, by simple modifications to the MWU method and the quasi-uniform sampling technique.

We present a number of new results about range searching for colored (or "categorical") data: 1. For a set of $n$ colored points in three dimensions, we describe randomized data structures with $O(n\mathop{\rm polylog}n)$ space that can report the distinct colors in any query orthogonal range (axis-aligned box) in $O(k\mathop{\rm polyloglog} n)$ expected time, where $k$ is the number of distinct colors in the range, assuming that coordinates are in $\{1,\ldots,n\}$. Previous data structures require $O(\frac{\log n}{\log\log n} + k)$ query time. Our result also implies improvements in higher constant dimensions. 2. Our data structures can be adapted to halfspace ranges in three dimensions (or circular ranges in two dimensions), achieving $O(k\log n)$ expected query time. Previous data structures require $O(k\log^2n)$ query time. 3. For a set of $n$ colored points in two dimensions, we describe a data structure with $O(n\mathop{\rm polylog}n)$ space that can answer colored "type-2" range counting queries: report the number of occurrences of every distinct color in a query orthogonal range. The query time is $O(\frac{\log n}{\log\log n} + k\log\log n)$, where $k$ is the number of distinct colors in the range. Naively performing $k$ uncolored range counting queries would require $O(k\frac{\log n}{\log\log n})$ time. Our data structures are designed using a variety of techniques, including colored variants of randomized incremental construction (which may be of independent interest), colored variants of shallow cuttings, and bit-packing tricks.

Given a set of n integer-valued coin types and a target value t, the well-known change-making problem asks for the minimum number of coins that sum to t, assuming an unlimited number of coins in each type. In the more general all-targets version of the problem, we want the minimum number of coins summing to j, for every j = 0,…,t. For example, the textbook dynamic programming algorithms can solve the all-targets problem in O(nt) time. Recently, Chan and He (SOSA'20) described a number of O(t polylog t)-time algorithms for the original (single-target) version of the change-making problem, but not the all-targets version. In this paper, we obtain a number of new results on change-making and related problems: - We present a new algorithm for the all-targets change-making problem with running time Õ(t^{4/3}), improving a previous Õ(t^{3/2})-time algorithm. - We present a very simple Õ(u²+t)-time algorithm for the all-targets change-making problem, where u denotes the maximum coin value. The analysis of the algorithm uses a theorem of Erdős and Graham (1972) on the Frobenius problem. This algorithm can be extended to solve the all-capacities version of the unbounded knapsack problem (for integer item weights bounded by u). - For the original (single-target) coin changing problem, we describe a simple modification of one of Chan and He’s algorithms that runs in Õ(u) time (instead of Õ(t)). - For the original (single-capacity) unbounded knapsack problem, we describe a simple algorithm that runs in Õ(nu) time, improving previous near-u²-time algorithms. - We also observe how one of our ideas implies a new result on the minimum word break problem, an optimization version of a string problem studied by Bringmann et al. (FOCS'17), generalizing change-making (which corresponds to the unary special case).

The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree Δ. In this article, we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as follows. Lower Bounds: First, we simplify the round elimination technique of Brandt et al. [16] and prove that (2Δ −2)-edge coloring requires Ω (log Δ log n ) time with high probability and Ω (log Δ n ) time deterministically, even on trees . Second, we show that a natural approach to computing (Δ +1)-edge colorings (Vizing’s theorem), namely, extending an arbitrary partial coloring by iteratively recoloring subgraphs, requires Ω (Δ log n ) time. Upper Bounds on General Graphs: We give a randomized edge coloring algorithm that can use palette sizes as small as Δ + Õ(√Δ), which is a natural barrier for randomized approaches. The running time of our (1+ϵ)Δ-edge coloring algorithm is usually dominated by O (\log ϵ −1 ) calls to a distributed Lovász local lemma (LLL) algorithm. For example, using the Chung-Pettie-Su LLL algorithm, we compute a (1+ϵ)Δ-edge coloring in O (log n ) time when ϵ ≥ (log 3 Δ) / √ Δ , or O (log Δ n ) + (log log n ) 3 + o (1) time when ϵ = Ω (1). When Δ is sublogarithmic in n the performance is improved with the Ghaffari-Harris-Kuhn LLL algorithm. Upper Bounds on Trees: We show that the Ω (log Δ log n ) lower bound can be nearly matched on trees. To establish this result, we develop a new distributed Lovász local lemma algorithm for tree-structured dependency graphs , which arise naturally from O (1)-round probabilistic algorithms run on trees. Specifically, our (1+ϵ)Δ-edge coloring algorithm for trees takes O (log (1 / ϵ)) ⋅ max { log log n \ log log log n , log log Δ log n } time when ϵ ≥ (log 3 Δ) / √ Δ, or O (max { log log n \ log log log n , log Δ log n }) time when ϵ = Ω (1).

Energy is often the most constrained resource in networks of batterypowered devices, and as devices become smaller, they spend a larger fraction of their energy on communication (transceiver usage) not computation. As an imperfect proxy for true energy usage, we define energy complexity to be the number of time slots a device transmits/listens; idle time and computation are free.

The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree Δ. In this paper we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as follows. We simplify the round elimination technique of Brandt et al. [9] and prove that (2Δ – 2)-edge coloring requires Ω(logΔ log n) time w.h.p. and Ω(logΔ n) time deterministically, even on trees. The simplified technique is based on two ideas: the notion of an irregular running time (in which network components terminate the algorithm at prescribed, but irregular times) and some general observations that transform weak lower bounds into stronger ones. We give a randomized edge coloring algorithm that can use palette sizes as small as , which is a natural barrier for randomized approaches. The running time of the algorithm is at most O(log Δ · TLLL), where TLLL is the complexity of a permissive version of the constructive Lovász local lemma. We develop a new distributed Lovász local lemma algorithm for tree-structured dependency graphs, which leads to a (1 + ∊)Δ-edge coloring algorithm for trees running in O(log log n) time. This algorithm arises from two new results: a deterministic O(log n)-time LLL algorithm for tree-structured instances, and a randomized O(log log n)-time graph shattering method for breaking the dependency graph into independent O(log n)-size LLL instances. A natural approach to computing (Δ + 1)-edge colorings (Vizing's theorem) is to extend partial colorings by iteratively re-coloring parts of the graph, e.g., via “augmenting paths.” We prove that this approach may be viable, but in the worst case requires recoloring subgraphs of diameter Ω(Δ log n). This stands in contrast to distributed algorithms for Brooks’ theorem [32], which exploit the existence of O(logΔ n)-length augmenting paths.