A $k$-spanner of a graph $G$ is a sparse subgraph that preserves its shortest path distances up to a multiplicative stretch factor of $k$, and a $k$-emulator is similar but not required to be a subgraph of $G$. A classic theorem by Thorup and Zwick [
JACM 05] shows that, despite the extra flexibility available to emulators, the size/stretch tradeoffs for spanners and emulators are equivalent. Our main result is that this equivalence in tradeoffs no longer holds in the commonly-studied setting of graphs with vertex failures. That is: we introduce a natural definition of vertex fault-tolerant emulators, and then we show a three-way tradeoff between size, stretch, and fault-tolerance for these emulators that polynomially surpasses the tradeoff known to be optimal for spanners. We complement our emulator upper bound with a lower bound construction that is essentially tight (within $log n$ factors of the upper bound) when the stretch is $2k-1$ and $k$ is either a fixed odd integer or $2$. We also show constructions of fault-tolerant emulators with additive error, demonstrating that these also enjoy significantly improved tradeoffs over those available for fault-tolerant additive spanners.
In this work, we study a scenario where a publisher seeks to maximize its total revenue across two sales channels: guaranteed contracts that promise to deliver a certain number of impressions to the advertisers, and spot demands through an Ad Exchang
e. On the one hand, if a guaranteed contract is not fully delivered, it incurs a penalty for the publisher. On the other hand, the publisher might be able to sell an impression at a high price in the Ad Exchange. How does a publisher maximize its total revenue as a sum of the revenue from the Ad Exchange and the loss from the under-delivery penalty? We study this problem parameterized by emph{supply factor $f$}: a notion we introduce that, intuitively, captures the number of times a publisher can satisfy all its guaranteed contracts given its inventory supply. In this work we present a fast simple deterministic algorithm with the optimal competitive ratio. The algorithm and the optimal competitive ratio are a function of the supply factor, penalty, and the distribution of the bids in the Ad Exchange. Beyond the yield optimization problem, classic online allocation problems such as online bipartite matching of [Karp-Vazirani-Vazirani 90] and its vertex-weighted variant of [Aggarwal et al. 11] can be studied in the presence of the additional supply guaranteed by the supply factor. We show that a supply factor of $f$ improves the approximation factors from $1-1/e$ to $f-fe^{-1/f}$. Our approximation factor is tight and approaches $1$ as $f to infty$.
Given a weighted undirected graph $G=(V,E,w)$, a hopset $H$ of hopbound $beta$ and stretch $(1+epsilon)$ is a set of edges such that for any pair of nodes $u, v in V$, there is a path in $G cup H$ of at most $beta$ hops, whose length is within a $(1+
epsilon)$ factor from the distance between $u$ and $v$ in $G$. We show the first efficient decremental algorithm for maintaining hopsets with a polylogarithmic hopbound. The update time of our algorithm matches the best known static algorithm up to polylogarithmic factors. All the previous decremental hopset constructions had a superpolylogarithmic (but subpolynomial) hopbound of $2^{log^{Omega(1)} n}$ [Bernstein, FOCS09; HKN, FOCS14; Chechik, FOCS18]. By applying our decremental hopset construction, we get improved or near optimal bounds for several distance problems. Most importantly, we show how to decrementally maintain $(2k-1)(1+epsilon)$-approximate all-pairs shortest paths (for any constant $k geq 2)$, in $tilde{O}(n^{1/k})$ amortized update time and $O(k)$ query time. This significantly improves (by a polynomial factor) over the update-time of the best previously known decremental algorithm in the constant query time regime. Moreover, it improves over the result of [Chechik, FOCS18] that has a query time of $O(log log(nW))$, where $W$ is the aspect ratio, and the amortized update time is $n^{1/k}cdot(frac{1}{epsilon})^{tilde{O}(sqrt{log n})}$. For sparse graphs our construction nearly matches the best known static running time/ query time tradeoff.
We give the first Congested Clique algorithm that computes a sparse hopset with polylogarithmic hopbound in polylogarithmic time. Given a graph $G=(V,E)$, a $(beta,epsilon)$-hopset $H$ with hopbound $beta$, is a set of edges added to $G$ such that fo
r any pair of nodes $u$ and $v$ in $G$ there is a path with at most $beta$ hops in $G cup H$ with length within $(1+epsilon)$ of the shortest path between $u$ and $v$ in $G$. Our hopsets are significantly sparser than the recent construction of Censor-Hillel et al. [6], that constructs a hopset of size $tilde{O}(n^{3/2})$, but with a smaller polylogarithmic hopbound. On the other hand, the previously known constructions of sparse hopsets with polylogarithmic hopbound in the Congested Clique model, proposed by Elkin and Neiman [10],[11],[12], all require polynomial rounds. One tool that we use is an efficient algorithm that constructs an $ell$-limited neighborhood cover, that may be of independent interest. Finally, as a side result, we also give a hopset construction in a variant of the low-memory Massively Parallel Computation model, with improved running time over existing algorithms.
There has been significant recent progress on algorithms for approximating graph spanners, i.e., algorithms which approximate the best spanner for a given input graph. Essentially all of these algorithms use the same basic LP relaxation, so a variety
of papers have studied the limitations of this approach and proved integrality gaps for this LP in a variety of settings. We extend these results by showing that even the strongest lift-and-project methods cannot help significantly, by proving polynomial integrality gaps even for $n^{Omega(epsilon)}$ levels of the Lasserre hierarchy, for both the directed and undirected spanner problems. We also extend these integrality gaps to related problems, notably Directed Steiner Network and Shallow-Light Steiner Network.
Data structures that allow efficient distance estimation (distance oracles, distance sketches, etc.) have been extensively studied, and are particularly well studied in centralized models and classical distributed models such as CONGEST. We initiate
their study in newer (and arguably more realistic) models of distributed computation: the Congested Clique model and the Massively Parallel Computation (MPC) model. We provide efficient constructions in both of these models, but our core results are for MPC. In MPC we give two main results: an algorithm that constructs stretch/space optimal distance sketches but takes a (small) polynomial number of rounds, and an algorithm that constructs distance sketches with worse stretch but that only takes polylogarithmic rounds. Along the way, we show that other useful combinatorial structures can also be computed in MPC. In particular, one key component we use to construct distance sketches are an MPC construction of the hopsets of Elkin and Neiman (2016). This result has additional applications such as the first polylogarithmic time algorithm for constant approximate single-source shortest paths for weighted graphs in the low memory MPC setting.
Solving linear programs is often a challenging task in distributed settings. While there are good algorithms for solving packing and covering linear programs in a distributed manner (Kuhn et al.~2006), this is essentially the only class of linear pro
grams for which such an algorithm is known. In this work we provide a distributed algorithm for solving a different class of convex programs which we call distance-bounded network design convex programs. These can be thought of as relaxations of network design problems in which the connectivity requirement includes a distance constraint (most notably, graph spanners). Our algorithm runs in $O( (D/epsilon) log n)$ rounds in the $mathcal{LOCAL}$ model and finds a $(1+epsilon)$-approximation to the optimal LP solution for any $0 < epsilon leq 1$, where $D$ is the largest distance constraint. While solving linear programs in a distributed setting is interesting in its own right, this class of convex programs is particularly important because solving them is often a crucial step when designing approximation algorithms. Hence we almost immediately obtain new and improved distributed approximation algorithms for a variety of network design problems, including Basic $3$- and $4$-Spanner, Directed $k$-Spanner, Lowest Degree $k$-Spanner, and Shallow-Light Steiner Network Design with a spanning demand graph. Our algorithms do not require any heavy computation and essentially match the best-known centralized approximation algorithms, while previous approaches which do not use heavy computation give approximations which are worse than the best-known centralized bounds.
