The Connectivity Augmentation Problem (CAP) is a fundamental problem in fault-tolerant network design and has been extensively studied in the context of approximation algorithms. In this work, we consider CAP in the online setting: given a \(k\)-edge-connected graph \(G\) and a set \(L\) of additional edges over the vertices of \(G\), called links, online requests arrive one by one, each specifying two vertices that need to be \((k + 1)\)-edge-connected. We start with the graph \(G\) and progressively add links to serve these requests. More specifically, upon the arrival of a request \(\{u, v\}\), we must immediately and irrevocably add zero or more links from \(L\) to the graph so that \(u\) and \(v\) are \((k + 1)\)-edge-connected in the resulting augmented graph. The goal is to minimize the total number of links added, and we evaluate an algorithm’s performance by its competitive ratio relative to an optimal offline solution. In this work, improving upon previous bounds, we obtain a tight competitive ratio for online CAP, along with other related results.

In this work we revisit the maximum range sum (MaxRS) problem which is well studied by the database and the computational geometry communities. The input is a set P of n weighted points in R d and a geometric range Q (typically either an axis-aligned d -box or a d -ball). The goal is to design a fast algorithm to place Q in R d so that the total weight of the points of P inside Q is maximized. We consider three natural variations of the MaxRS problem: In the dynamic MaxRS problem, points are inserted and deleted, and the goal is to efficiently update the placement of a d -ball. In R d we present a randomized (1/2 - ε)-approximation algorithm with update time O ε (log n). The approximation factor holds with high probability. To the best of our knowledge, this problem was not studied before in the literature. In the batched MaxRS problem in R 1 , along with the points in P we are given m intervals of different lengths. The goal is to solve the MaxRS problem for each interval. We establish a conditional lower bound of Ω(mn) time for this problem, assuming the hardness of (min,+)-convolution problem. Interestingly, this implies that the trivial upper bound of O(mn log n) for batched MaxRS in R 2 is almost-tight. A similar lower bound is established for a related problem of batched smallest k -enclosing interval. In the colored MaxRS problem in R d , each point in P is assigned a color from {1,2,...,m} and the goal is to find the placement of a d -ball Q that maximizes the number of uniquely colored points in P ∩ Q. Prior work on this problem was limited to axis-aligned rectangle Q in R 2 . We obtain two new results for d -balls. The first result is a randomized (1/2 - ε)-approximation algorithm with running time O ε (n log n). Interestingly, the exponential dependence of log n on d is avoided in the running time. The second result improves upon the first result in R 2 by providing a (1-ε)-approximation algorithm with expected running time O_ε(n log n). The approximation factor holds with high probability for both results. Our algorithms are obtained via two general techniques which we believe will be useful for solving other variants of MaxRS. The first technique provides a (1/2 - ε)-approximation guarantee. The analysis relies on a volume argument involving d -balls and a randomized game. The second technique provides a (1-ε)-approximation guarantee and works in two phases. In the first phase, we design an exact output-sensitive algorithm, and in the second phase, we speed up the exact algorithm by random sampling on colors.

We study the problem of stabbing rectilinear polygons, where we are given $n$ rectilinear polygons in the plane that we want to stab, i.e., we want to select horizontal line segments such that for each given rectilinear polygon there is a line segment that intersects two opposite (parallel) edges of it. Our goal is to find a set of line segments of minimum total length such that all polygons are stabbed. For the special case of rectangles, there is a $O(1)$-approximation algorithm and the problem is $\mathsf{NP}$-hard [Chan et al.]. Also, the problem admits a QPTAS [Eisenbrand et al.] and even a PTAS [Khan et al.]. However, the approximability for the setting of more general polygons, e.g., L-shapes or T-shapes, is completely open. In this paper, we characterize the conditions under which the problem admits a $(1+\varepsilon)$-approximation algorithm. We assume that each input polygon is composed of rectangles that are placed on top of each other such that, for each pair of adjacent edges between rectangles, one edge contains the other. We show that if all input polygons satisfy the hourglass condition, then the problem admits a QPTAS. In particular, it is thus unlikely that this case is $\mathsf{APX}$-hard. Furthermore, we show that there exists a PTAS if each input polygon is composed out of rectangles with a bounded range of widths. On the other hand, if the input polygons do not satisfy these conditions, we prove that the problem is $\mathsf{APX}$-hard, already if all input polygons have only eight edges. We remark that all polygons with fewer edges automatically satisfy the hourglass condition. On the other hand, for arbitrary rectilinear polygons we even show a lower bound of $Ω(\log n)$ for the possible approximation ratio, which implies that the best possible ratio is in $Θ(\log n)$ since the problem is a special case of Set Cover.

Set cover and hitting set are fundamental problems in combinatorial optimization which are well-studied in the offline, online, and dynamic settings. We study the geometric versions of these problems and present new online and dynamic algorithms for them. In the online version of set cover (resp. hitting set), $m$ sets (resp.~$n$ points) are give $n$ points (resp.~$m$ sets) arrive online, one-by-one. In the dynamic versions, points (resp. sets) can arrive as well as depart. Our goal is to maintain a set cover (resp. hitting set), minimizing the size of the computed solution. For online set cover for (axis-parallel) squares of arbitrary sizes, we present a tight $O(\log n)$-competitive algorithm. In the same setting for hitting set, we provide a tight $O(\log N)$-competitive algorithm, assuming that all points have integral coordinates in $[0,N)^{2}$. No online algorithm had been known for either of these settings, not even for unit squares (apart from the known online algorithms for arbitrary set systems). For both dynamic set cover and hitting set with $d$-dimensional hyperrectangles, we obtain $(\log m)^{O(d)}$-approximation algorithms with $(\log m)^{O(d)}$ worst-case update time. This partially answers an open question posed by Chan et al. [SODA'22]. Previously, no dynamic algorithms with polylogarithmic update time were known even in the setting of squares (for either of these problems). Our main technical contributions are an \emph{extended quad-tree }approach and a \emph{frequency reduction} technique that reduces geometric set cover instances to instances of general set cover with bounded frequency.

Ranking algorithms find extensive usage in diverse areas such as web search, employment, college admission, voting, etc. The related rank aggregation problem deals with combining multiple rankings into a single aggregate ranking. However, algorithms for both these problems might be biased against some individuals or groups due to implicit prejudice or marginalization in the historical data. We study ranking and rank aggregation problems from a fairness or diversity perspective, where the candidates (to be ranked) may belong to different groups and each group should have a fair representation in the final ranking. We allow the designer to set the parameters that define fair representation. These parameters specify the allowed range of the number of candidates from a particular group in the top-$k$ positions of the ranking. Given any ranking, we provide a fast and exact algorithm for finding the closest fair ranking for the Kendall tau metric under {\em strong fairness}, i.e., when the final ranking is fair for all values of $k$. We also provide an exact algorithm for finding the closest fair ranking for the Ulam metric under strong fairness when there are only $O(1)$ number of groups. Our algorithms are simple, fast, and might be extendable to other relevant metrics. We also give a novel meta-algorithm for the general rank aggregation problem under the fairness framework. Surprisingly, this meta-algorithm works for any generalized mean objective (including center and median problems) and any fairness criteria. As a byproduct, we obtain 3-approximation algorithms for both center and median problems, under both Kendall tau and Ulam metrics. Furthermore, using sophisticated techniques we obtain a $(3-\varepsilon)$-approximation algorithm, for a constant $\varepsilon>0$, for the Ulam metric under strong fairness.