Bilò, Davide; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Krogmann, Simon; Schirneck, Martin Compact Distance Oracles with Large Sensitivity and Low StretchAlgorithms and Data Structures Symposium (WADS) 2023: 149–163
An \(f\)-edge fault-tolerant distance sensitive oracle (\(f\)-DSO) with stretch \(\sigma \geq 1\) is a data-structure that preprocesses an input graph \(G = (V,E)\). When queried with the triple \((s,t,F)\), where \(s, t \in V\) and \(F \subseteq E\) contains at most \(f\) edges of \(G\), the oracle returns an estimate \(\widehat{d}_{G-F}(s,t)\) of the distance \(d_{G-F}(s,t)\) between \(s\) and \(t\) in the graph \(G-F\) such that \(d_{G-F}(s,t) leq \widehat{d}_{G-F}(s,t) leq sigma cdot d_{G-F}(s,t)\). For any positive integer \(k \ge 2\) and any \(0 < \alpha < 1\), we present an \(f\)-DSO with sensitivity \(f = o(\log n/\log\log n)\), stretch \(2k-1\), space \(O(n^{1+\frac{1}{k}+\alpha+o(1)})\), and an \(\widetilde{O}(n^{1+\frac{1}{k} - \frac{\alpha}{k(f+1)}})\) query time. Prior to our work, there were only three known \(f\)-DSOs with subquadratic space. The first one by Chechik et al. [Algorithmica 2012] has a stretch of \((8k-2)(f+1)\), depending on \(f\). Another approach is storing an \(f\)-edge fault-tolerant \((2k-1)\)-spanner of \(G\). The bottleneck is the large query time due to the size of any such spanner, which is \(\Omega(n^{1+1/k})\) under the Erdős girth conjecture. Bilò et al. [STOC 2023] gave a solution with stretch \(3+\varepsilon\), query time \(O(n^{\alpha})\) but space \(O(n^{2-\frac{\alpha}{f+1}})\), approaching the quadratic barrier for large sensitivity. In the realm of subquadratic space, our \(f\)-DSOs are the first ones that guarantee, at the same time, large sensitivity, low stretch, and non-trivial query time. To obtain our results, we use the approximate distance oracles of Thorup and Zwick [JACM 2005], and the derandomization of the \(f\)-DSO of Weimann and Yuster [TALG 2013] that was recently given by Karthik and Parter [SODA 2021].
Bandyapadhyay, Sayan; Fomin, Fedor V.; Inamdar, Tanmay; Panolan, Fahad; Simonov, Kirill Socially Fair Matching: Exact and Approximation AlgorithmsWorkshop on Algorithms and Data Structures (WADS) 2023: 79–92
Matching problems are some of the most well-studied problems in graph theory and combinatorial optimization, with a variety of theoretical as well as practical motivations. However, in many applications of optimization problems, a ``solution'' corresponds to real-life decisions that have major impact on humans belonging to diverse groups defined by attributes such as gender, race, or ethnicity. Due to this motivation, the notion of \emph{algorithmic fairness} has recently emerged to prominence. Depending on specific application, researchers have introduced several notions of fairness. In this paper, we study a problem called ``Socially Fair Matching'', which combines the traditional Minimum Weight Perfect Matching problem with the notion of social fairness that has been studied in clustering literature [Abbasi et al., and Ghadiri et al., FAccT, 2021]. In our problem, the input is an edge-weighted complete bipartite graph, where the bipartition represent two groups of entities. The goal is to find a perfect matching as well as an assignment that assigns the cost of each matched edge to one of its endpoints, such that the maximum of the total cost assigned to either of the two groups is minimized. Unlike Minimum Weight Perfect Matching, we show that Socially Fair Matching is weakly NP-hard. On the positive side, we design a deterministic PTAS for the problem when the edge weights are arbitrary. Furthermore, if the weights are integers and polynomial in the number of vertices, then we give a randomized polynomial-time algorithm that solves the problem exactly. Next, we show that this algorithm can be used to obtain a randomized FPTAS when the weights are arbitrary.