More Like this

1. Dynamic Geometric Set Cover and Hitting Set

   Agarwal, P; Chang, H; Suri, S; Xiao, A; Xue, J. (June 2020, 36th International Symposium on Computational Geometry (SoCG 2020).)

   We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) optimal solution for the current problem instance. While their static versions have been extensively studied in the past, surprisingly little is known about dynamic geometric set cover and hitting set. For instance, even for the most basic case of one-dimensional interval set cover and hitting set, no nontrivial results were known. The main contribution of our paper are two frameworks that lead to efficient data structures. 

   more » « less
2. Subtrajectory Clustering: Finding Set Covers for Set Systems of Subcurves

   Brüning, F.; Akitaya, H.; Chambers, E; Driemel, A (February 2023, Computing in geometry and topology)

   We study subtrajectory clustering under the Fréchet distance. Given one or more trajectories, the task is to split the trajectories into several parts, such that the parts have a good clustering structure. We approach this problem via a new set cover formulation, which we think provides a natural formalization of the problem as it is studied in many applications. Given a polygonal curve P with n vertices in fixed dimension, integers k, ℓ ≥ 1, and a real value Δ > 0, the goal is to find k center curves of complexity at most ℓ such that every point on P is covered by a subtrajectory that has small Fréchet distance to one of the k center curves (≤ Δ). In many application scenarios, one is interested in finding clusters of small complexity, which is controlled by the parameter ℓ. Our main result is a bicriterial approximation algorithm: if there exists a solution for given parameters k, ℓ, and Δ, then our algorithm finds a set of k' center curves of complexity at most ℓ with covering radius Δ' with k' in O(kℓ2 log (kℓ)), and Δ' ≤ 19Δ. Moreover, within these approximation bounds, we can minimize k while keeping the other parameters fixed. If ℓ is a constant independent of n, then, the approximation factor for the number of clusters k is O(log k) and the approximation factor for the radius Δ is constant. In this case, the algorithm has expected running time in Õ(km2 + mn) and uses space in O(n + m), where m=⌈L/Δ⌉ and L is the total arclength of the curve P. 

   more » « less
3. Down‐set thresholds

   https://doi.org/10.1002/rsa.21148  

   Gunby, Benjamin; He, Xiaoyu; Narayanan, Bhargav (September 2023, Random Structures & Algorithms)

   We elucidate the relationship between the threshold and the expectation-threshold of a down-set. Qualitatively, our main result demonstrates that there exist down-sets with polynomial gaps between their thresholds and expectation-thresholds; in particular, the logarithmic gap predictions of Kahn--Kalai and Talagrand (recently proved by Park--Pham and Frankston--Kahn--Narayanan--Park) about up-sets do not apply to down-sets. Quantitatively, we show that any collection $$\cG$$ of graphs on $[n]$ that covers the family of all triangle-free graphs on $[n]$ satisfies the inequality $$\sum_{G \in \cG} \exp(-\delta e(G^c) / \sqrt{n}) < 1/2$$ for some universal $$\delta > 0$$, and this is essentially best-possible. 

   more » « less
4. Training Set Camouflage

   https://doi.org/10.1007/978-3-030-01554-1_4  

   Sen, Ayon; Alfeld, Scott; Zhang, Xuezhou; Vartanian, Ara; Ma, Yuzhe; Zhu, Xiaojin (January 2019, International Conference on Decision and Game Theory for Security)
5. Fair Set Cover

   https://doi.org/10.1145/3690624.3709184  

   Dehghankar, Mohsen; Raychaudhury, Rahul; Sintos, Stavros; Asudeh, Abolfazl (July 2025, ACM SIGKDD Conference on Knowledge Discovery and Data Mining)