This paper considers using predictions in the context of the online Joint Replenishment Problem with Deadlines (JRP-D). Prior work includes asymptotically optimal competitive ratios of $O(1)$ for the clairvoyant setting and $O(\sqrt{n})$ of the nonclairvoyant setting, where $n$ is the number of items. The goal of this paper is to significantly reduce the competitive ratio for the nonclairvoyant case by leveraging predictions: when a request arrives, the true deadline of the request is not revealed, but the algorithm is given a predicted deadline. The main result is an algorithm whose competitive ratio is $O(\min(η^{1/3}\log^{2/3}(n), \sqrtη, \sqrt{n}))$, where $n$ is the number of item types and $η\leq n^2$ quantifies how flawed the predictions are in terms of the number of ``instantaneous item inversions.'' Thus, the algorithm is robust, i.e., it is never worse than the nonclairvoyant solution, and it is consistent, i.e., if the predictions exhibit no inversions, then the algorithm behaves similarly to the clairvoyant algorithm. Moreover, if the error is not too large, specifically $η< o(n^{3/2}/\log^2(n))$, then the algorithm obtains an asymptotically better competitive ratio than the nonclairvoyant algorithm. We also show that all deterministic algorithms falling in a certain reasonable class of algorithms have a competitive ratio of $Ω(η^{1/3})$, so this algorithm is nearly the best possible with respect to this error metric.

In this paper, we address the challenge of differential privacy in the context of graph cuts, specifically focusing on the multiway cut and the minimum \(k\)-cut. We introduce edge-differentially private algorithms that achieve nearly optimal performance for these problems. Motivated by multiway cut, we propose the shifting mechanism, a general framework for private combinatorial optimization problems. This framework allows us to develop an efficient private algorithm with a multiplicative approximation ratio that matches the state-of-the-art non-private algorithm, improving over previous private algorithms that have provably worse multiplicative loss. We then provide a tight information-theoretic lower bound on the additive error, demonstrating that for constant \(k\), our algorithm is optimal in terms of the privacy cost. The shifting mechanism also allows us to design private algorithm for the multicut and max-cut problems, with runtimes determined by the best nonprivate algorithms for these tasks. For the minimum \(k\)-cut problem we use a different approach, combining the exponential mechanism with bounds on the number of approximate \(k\)-cuts to get the first private algorithm with optimal additive error of \(O(k \log n)\) (for a fixed privacy parameter). We also establish an information-theoretic lower bound that matches this additive error. Furthermore, we provide an efficient private algorithm even for non-constant \(k\), including a polynomial-time 2-approximation with an additive error of \(\tilde O(k^{1.5})\).

There has recently been significant interest in fault tolerant spanners, which are spanners that still maintain their stretch guarantees after some nodes or edges fail. This work has culminated in an almost complete understanding of the three-way tradeoff between stretch, sparsity, and number of faults tolerated. However, despite some progress in metric settings, there have been no results to date on the tradeoff in general graphs between stretch, lightness, and number of faults tolerated. We initiate the study of light edge fault tolerant (EFT) graph spanners, obtaining the first such results. First, we observe that lightness can be unbounded if we use the traditional definition (normalizing by the MST). We then argue that a natural definition of fault-tolerant lightness is to instead normalize by a min-weight fault tolerant connectivity preserver; essentially, a fault-tolerant version of the MST. However, even with this, we show that it is still not generally possible to construct $f$-EFT spanners whose weight compares reasonably to the weight of a min-weight $f$-EFT connectivity preserver. In light of this lower bound, it is natural to then consider bicriteria notions of lightness, where we compare the weight of an $f$-EFT spanner to a min-weight $(f' > f)$-EFT connectivity preserver. The most interesting question is to determine the minimum value of $f'$ that allows for reasonable lightness upper bounds. Our main result is a precise answer to this question: $f' = 2f$. In particular, we show that the lightness can be untenably large (roughly $n/k$ for a $k$-spanner) if one normalizes by the min-weight $(2f-1)$-EFT connectivity preserver. But if one normalizes by the min-weight $2f$-EFT connectivity preserver, then we show that the lightness is bounded by just $O(f^{1/2})$ times the non-fault tolerant lightness (roughly $n^{1/k}$, for a $(1+ε)(2k-1)$-spanner).

For a given graph G, a hopset H with hopbound β and stretch α is a set of edges such that between every pair of vertices u and v, there is a path with at most β hops in G ∪ H that approximates the distance between u and v up to a multiplicative stretch of α. Hopsets have found a wide range of applications for distance-based problems in various computational models since the 90s. More recently, there has been significant interest in understanding these fundamental objects from an existential and structural perspective. But all of this work takes a worst-case (or existential) point of view: How many edges do we need to add to satisfy a given hopbound and stretch requirement for any input graph? We initiate the study of the natural optimization variant of this problem: given a specific graph instance, what is the minimum number of edges that satisfy the hopbound and stretch requirements? We give approximation algorithms for a generalized hopset problem which, when combined with known existential bounds, lead to different approximation guarantees for various regimes depending on hopbound, stretch, and directed vs. undirected inputs. We complement our upper bounds with a lower bound that implies Label Cover hardness for directed hopsets and shortcut sets with hopbound at least 3.

We study the problem of approximating all-pair distances in a weighted undirected graph with differential privacy, introduced by Sealfon [Sea16]. Given a publicly known undirected graph, we treat the weights of edges as sensitive information, and two graphs are neighbors if their edge weights differ in one edge by at most one. We obtain efficient algorithms with significantly improved bounds on a broad class of graphs which we refer to as *recursively separable*. In particular, for any $n$-vertex $K_h$-minor-free graph, our algorithm achieve an additive error of $ \widetilde{O}(h(nW)^{1/3} ) $, where $ W $ represents the maximum edge weight; For grid graphs, the same algorithmic scheme achieve additive error of $ \widetilde{O}(n^{1/4}\sqrt{W}) $. Our approach can be seen as a generalization of the celebrated binary tree mechanism for range queries, as releasing range queries is equivalent to computing all-pair distances on a path graph. In essence, our approach is based on generalizing the binary tree mechanism to graphs that are *recursively separable*.

We study the Densest Subgraph (DSG) problem under the additional constraint of differential privacy. DSG is a fundamental theoretical question that plays a central role in graph analytics, and so privacy is a natural requirement. All known private algorithms for Densest Subgraph lose constant multiplicative factors, despite the existence of non-private exact algorithms. We show that, perhaps surprisingly, this loss is not necessary: in both the classic differential privacy model and the LEDP model (local edge differential privacy, introduced recently by Dhulipala et al. [FOCS 2022]), we give (ϵ, δ)-differentially private algorithms with no multiplicative loss whatsoever. In other words, the loss is purely additive. Moreover, our additive losses match or improve the previous state of the art additive loss (in any version of differential privacy) when 1/δ is polynomial in n, and are almost tight: in the centralized setting, our additive loss is O (log n/ϵ ) while there is a known lower bound of .

Emerging reconfigurable optical communication technologies allow to enhance datacenter topologies with demand-aware links optimized towards traffic patterns. This paper studies the algorithmic problem of jointly optimizing topology and routing in such demand-aware networks to minimize congestion, along two dimensions: (1) splittable or unsplittable flows, and (2) whether routing is segregated, i.e., whether routes can or cannot combine both demand-aware and demand-oblivious (static) links.For splittable and segregated routing, we show that the problem is generally 2-approximable, but APX-hard even for uniform demands induced by a bipartite demand graph. For unsplittable and segregated routing, we establish upper and lower bounds of O (log m/ log log m) and Ω (log m/ log log m), respectively, for polynomial-time approximation algorithms, where m is the number of static links. We further reveal that under un-/splittable and non-segregated routing, even for demands of a single source (resp., d estina tion), the problem cannot be approximated better than $\Omega \left({\frac{{{c_{\max }}}}{{{c_{\min }}}}}\right)$ unless P=NP, where cmax(resp., cmin) denotes the maximum (resp., minimum) capacity. It remains NP-hard for uniform capacities, but is tractable for a single commodity and uniform capacities.Our trace-driven simulations show a significant reduction in network congestion compared to existing solutions.

Algorithms with (machine-learned) predictions is a powerful framework for combining traditional worst-case algorithms with modern machine learning. However, the vast majority of work in this space assumes that the prediction itself is non-probabilistic, even if it is generated by some stochastic process (such as a machine learning system). This is a poor fit for modern ML, particularly modern neural networks, which naturally generate a *distribution*. We initiate the study of algorithms with *distributional* predictions, where the prediction itself is a distribution. We focus on one of the simplest yet fundamental settings: binary search (or searching a sorted array). This setting has one of the simplest algorithms with a point prediction, but what happens if the prediction is a distribution? We show that this is a richer setting: there are simple distributions where using the classical prediction-based algorithm with any single prediction does poorly. Motivated by this, as our main result, we give an algorithm with query complexity $O(H(p) + \log \eta)$, where $H(p)$ is the entropy of the true distribution $p$ and $\eta$ is the earth mover's distance between $p$ and the predicted distribution $\hat p$. This also yields the first *distributionally-robust* algorithm for the classical problem of computing an optimal binary search tree given a distribution over target keys. We complement this with a lower bound showing that this query complexity is essentially optimal (up to constants), and experiments validating the practical usefulness of our algorithm.

The classical ski-rental problem admits a textbook 2-competitive deterministic algorithm, and a simple randomized algorithm that is e/e-1-competitive in expectation. The randomized algorithm, while optimal in expectation, has a large variance in its performance: it has more than a 37% chance of competitive ratio exceeding 2, and the change of the competitive ratio exceeding n is Θ(1/n)!

The SetCover problem has been extensively studied in many different models of computation, including parallel and distributed settings. From an approximation point of view, there are two standard guarantees: an O(log Δ)-approximation (where Δ is the maximum set size) and an O(f)-approximation (where f is the maximum number of sets containing any given element). In this paper, we introduce a new, surprisingly simple, model-independent approach to solving SetCover in unweighted graphs. We obtain multiple improved algorithms in the MPC and CRCW PRAM models. First, in the MPC model with sublinear space per machine, our algorithms can compute an O(f) approximation to SetCover in Ô(√{log Δ} + log f) rounds and a O(log Δ) approximation in O(log^{3/2} n) rounds. Moreover, in the PRAM model, we give a O(f) approximate algorithm using linear work and O(log n) depth. All these bounds improve the existing round complexity/depth bounds by a log^{Ω(1)} n factor. Moreover, our approach leads to many other new algorithms, including improved algorithms for the HypergraphMatching problem in the MPC model, as well as simpler SetCover algorithms that match the existing bounds.

The best known solutions for k -message broadcast in dynamic networks of size n require Ω ( nk ) rounds. In this article, we see if these bounds can be improved by smoothed analysis. To do so, we study perhaps the most natural randomized algorithm for disseminating tokens in this setting: at every timestep, choose a token to broadcast randomly from the set of tokens you know. We show that with even a small amount of smoothing (i.e., one random edge added per round), this natural strategy solves k -message broadcast in \(\tilde{O}(n+k^3)\) rounds, with high probability, beating the best known bounds for \(k=o(\sqrt {n})\) and matching the Ω ( n + k ) lower bound for static networks for k = O ( n 1/3 ) (ignoring logarithmic factors). In fact, the main result we show is even stronger and more general: Given ℓ-smoothing (i.e., ℓ random edges added per round), this simple strategy terminates in \(O(kn^{2/3}\log ^{1/3}(n)\ell ^{-1/3})\) rounds. We then prove this analysis close to tight with an almost-matching lower bound. To better understand the impact of smoothing on information spreading, we next turn our attention to static networks, proving a tight bound of \(\tilde{O}(k\sqrt {n})\) rounds to solve k -message broadcast, which is better than what our strategy can achieve in the dynamic setting. This confirms the intuition that although smoothed analysis reduces the difficulties induced by changing graph structures, it does not eliminate them altogether. Finally, we apply tools developed to support our smoothed analysis to prove an optimal result for k -message broadcast in so-called well-mixed networks in the absence of smoothing. By comparing this result to an existing lower bound for well-mixed networks, we establish a formal separation between oblivious and strongly adaptive adversaries with respect to well-mixed token spreading, partially resolving an open question on the impact of adversary strength on the k -message broadcast problem.

A $t$-emulator of a graph $G$ is a graph $H$ that approximates its pairwise shortest path distances up to multiplicative $t$ error. We study fault tolerant $t$-emulators, under the model recently introduced by Bodwin, Dinitz, and Nazari [ITCS 2022] for vertex failures. In this paper we consider the version for edge failures, and show that they exhibit surprisingly different behavior. In particular, our main result is that, for $(2k-1)$-emulators with $k$ odd, we can tolerate a polynomial number of edge faults for free. For example: for any $n$-node input graph, we construct a $5$-emulator ($k=3$) on $O(n^{4/3})$ edges that is robust to $f = O(n^{2/9})$ edge faults. It is well known that $Ω(n^{4/3})$ edges are necessary even if the $5$-emulator does not need to tolerate any faults. Thus we pay no extra cost in the size to gain this fault tolerance. We leave open the precise range of free fault tolerance for odd $k$, and whether a similar phenomenon can be proved for even $k$.

The spread of an epidemic is often modeled by an SIR random process on a social network graph. The MinInfEdge problem for optimal social distancing involves minimizing the expected number of infections, when we are allowed to break at most B edges; similarly the MinInfNode problem involves removing at most B vertices. These are fundamental problems in epidemiology and network science. While a number of heuristics have been considered, the complexity of this problem remains generally open. In this paper, we present two bicriteria approximation algorithms for the MinInfEdge problem, which give the first non-trivial approximations for this problem. The first is based on the cut sparsification result technique of Karger, which works for any graph, when the transmission probabilities are not too small. The second is a Sample Average Approximation (SAA) based algorithm, which we analyze for the Chung-Lu random graph model. We also extend some of our results for the MinInfNode problem.

Graph cut problems are fundamental in combinatorial Optimization, and are a central object of study in both theory and practice. Further, the study of fairness in Algorithmic Design and Machine Learning has recently received significant attention, with many different notions proposed and analyzed for a variety of contexts. In this paper we initiate the study of fairness for graph cut problems by giving the first fair definitions for them, and subsequently we demonstrate appropriate algorithmic techniques that yield a rigorous theoretical analysis. Specifically, we incorporate two different notions of fairness, namely demographic and probabilistic individual fairness, in a particular cut problem that models disaster containment scenarios. Our results include a variety of approximation algorithms with provable theoretical guarantees.

One of the most important and well-studied settings for network design is edge-connectivity requirements. This encompasses uniform demands such as the Minimum $k$-Edge-Connected Spanning Subgraph problem ($k$-ECSS), as well as nonuniform demands such as the Survivable Network Design problem. A weakness of these formulations, though, is that we are not able to ask for fault-tolerance larger than the connectivity. We introduce and study new variants of these problems under a notion of relative fault-tolerance. Informally, we require not that two nodes are connected if there are a bounded number of faults (as in the classical setting), but that two nodes are connected if there are a bounded number of faults and the two nodes are connected in the underlying graph post-faults. That is, the subgraph we build must "behave" identically to the underlying graph with respect to connectivity after bounded faults. We define and introduce these problems, and provide the first approximation algorithms: a $(1+4/k)$-approximation for the unweighted relative version of $k$-ECSS, a $2$-approximation for the weighted relative version of $k$-ECSS, and a $27/4$-approximation for the special case of Relative Survivable Network Design with only a single demand with a connectivity requirement of $3$. To obtain these results, we introduce a number of technical ideas that may of independent interest. First, we give a generalization of Jain's iterative rounding analysis that works even when the cut-requirement function is not weakly supermodular, but instead satisfies a weaker definition we introduce and term local weak supermodularity. Second, we prove a structure theorem and design an approximation algorithm utilizing a new decomposition based on important separators, which are structures commonly used in fixed-parameter algorithms that have not commonly been used in approximation algorithms.

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.

The research area of algorithms with predictions has seen recent success showing how to incorporate machine learning into algorithm design to improve performance when the predictions are correct, while retaining worst-case guarantees when they are not. Most previous work has assumed that the algorithm has access to a single predictor. However, in practice, there are many machine learning methods available, often with incomparable generalization guarantees, making it hard to pick a best method a priori. In this work we consider scenarios where multiple predictors are available to the algorithm and the question is how to best utilize them. Ideally, we would like the algorithm's performance to depend on the quality of the {\em best} predictor. However, utilizing more predictions comes with a cost, since we now have to identify which prediction is best. We study the use of multiple predictors for a number of fundamental problems, including matching, load balancing, and non-clairvoyant scheduling, which have been well-studied in the single predictor setting. For each of these problems we introduce new algorithms that take advantage of multiple predictors, and prove bounds on the resulting performance.

Recent work has established that, for every positive integer k, every n-node graph has a (2k–1)-spanner with O(f1–1/k n1+1/k) edges that is resilient to f edge or vertex faults. For vertex faults, this bound is tight. However, the case of edge faults is not as well understood: the best known lower bound for general k is . Our main result is to nearly close this gap with an improved upper bound, thus separating the cases of edge and vertex faults. For odd k, our new upper bound is , which is tight up to hidden poly(k) factors. For even k, our new upper bound is Ok(f1/2 n1 + 1/k + fn), which leaves a gap of poly(k)f1/(2k). Our proof is an analysis of the fault-tolerant greedy algorithm, which requires exponential time, but we also show that there is a polynomial-time algorithm which creates edge fault tolerant spanners that are larger only by factors of k.

The best known solutions for $k$-message broadcast in dynamic networks of size $n$ require $Ω(nk)$ rounds. In this paper, we see if these bounds can be improved by smoothed analysis. We study perhaps the most natural randomized algorithm for disseminating tokens in this setting: at every time step, choose a token to broadcast randomly from the set of tokens you know. We show that with even a small amount of smoothing (one random edge added per round), this natural strategy solves $k$-message broadcast in $\tilde{O}(n+k^3)$ rounds, with high probability, beating the best known bounds for $k=o(\sqrt{n})$ and matching the $Ω(n+k)$ lower bound for static networks for $k=O(n^{1/3})$ (ignoring logarithmic factors). In fact, the main result we show is even stronger and more general: given $\ell$-smoothing (i.e., $\ell$ random edges added per round), this simple strategy terminates in $O(kn^{2/3}\log^{1/3}(n)\ell^{-1/3})$ rounds. We then prove this analysis close to tight with an almost-matching lower bound. To better understand the impact of smoothing on information spreading, we next turn our attention to static networks, proving a tight bound of $\tilde{O}(k\sqrt{n})$ rounds to solve $k$-message broadcast, which is better than what our strategy can achieve in the dynamic setting. This confirms that although smoothed analysis reduces the difficulties induced by changing graph structures, it does not eliminate them altogether. Finally, we apply our tools to prove an optimal result for $k$-message broadcast in so-called well-mixed networks in the absence of smoothing. By comparing this result to an existing lower bound for well-mixed networks, we establish a formal separation between oblivious and strongly adaptive adversaries with respect to well-mixed token spreading, partially resolving an open question on the impact of adversary strength on the $k$-message broadcast problem.

A recent line of research investigates how algorithms can be augmented with machine-learned predictions to overcome worst case lower bounds. This area has revealed interesting algorithmic insights into problems, with particular success in the design of competitive online algorithms. However, the question of improving algorithm running times with predictions has largely been unexplored. We take a first step in this direction by combining the idea of machine-learned predictions with the idea of ``warm-starting" primal-dual algorithms. We consider one of the most important primitives in combinatorial optimization: weighted bipartite matching and its generalization to $b$-matching. We identify three key challenges when using learned dual variables in a primal-dual algorithm. First, predicted duals may be infeasible, so we give an algorithm that efficiently maps predicted infeasible duals to nearby feasible solutions. Second, once the duals are feasible, they may not be optimal, so we show that they can be used to quickly find an optimal solution. Finally, such predictions are useful only if they can be learned, so we show that the problem of learning duals for matching has low sample complexity. We validate our theoretical findings through experiments on both real and synthetic data. As a result we give a rigorous, practical, and empirically effective method to compute bipartite matchings.

Recent work has pinned down the existentially optimal size bounds for vertex fault-tolerant spanners: for any positive integer k, every n-node graph has a (2k – 1)-spanner on O(f1–1/kn1+1/k) edges resilient to f vertex faults, and there are examples of input graphs on which this bound cannot be improved. However, these proofs work by analyzing the output spanner of a certain exponential-time greedy algorithm. In this work, we give the first algorithm that produces vertex fault tolerant spanners of optimal size and which runs in polynomial time. Specifically, we give a randomized algorithm which takes Õ (f1–1/kn2+1/k + mf2) time. We also derandomize our algorithm to give a deterministic algorithm with similar bounds. This reflects an exponential improvement in runtime over [Bodwin-Patel PODC '19], the only previously known algorithm for constructing optimal vertex fault-tolerant spanners.

New optical technologies offer the ability to reconfigure network topologies dynamically, rather than setting them once and for all. This is true in both optical wide area networks (optical WANs) and in datacenters, despite the many differences between these two settings. Because of these new technologies, there has been a surge of both practical and theoretical research on algorithms to take advantage of them. In particular, Jia et al. [INFOCOM '17] designed online scheduling algorithms for dynamically reconfigurable topologies for both the makespan and sum of completion times objectives. In this paper, we work in the same setting but study an objective that is more meaningful in an online setting: the sum of flow times. The flow time of a job is the total amount of time that it spends in the system, which may be considerably smaller than its completion time if it is released late. We provide competitive algorithms for the online setting with speed augmentation, and also give a lower bound proving that speed augmentation is in fact necessary. As a side effect of our techniques, we also improve and generalize the results of Jia et al. on completion times by giving an O(1)-competitive algorithm for arbitrary sizes and release times even when nodes have different degree bounds, and moreover allow for the weighted sum of completion times (or flow times).

It was recently shown that a version of the greedy algorithm gives a construction of fault-tolerant spanners that is size-optimal, at least for vertex faults. However, the algorithm to construct this spanner is not polynomial-time, and the best-known polynomial time algorithm is significantly suboptimal. Designing a polynomial-time algorithm to construct (near-)optimal fault-tolerant spanners was given as an explicit open problem in the two most recent papers on fault-tolerant spanners ([Bodwin, Dinitz, Parter, Vassilevka Williams SODA '18] and [Bodwin, Patel PODC '19]). We give a surprisingly simple algorithm which runs in polynomial time and constructs fault-tolerant spanners that are extremely close to optimal (off by only a linear factor in the stretch) by modifying the greedy algorithm to run in polynomial time. To complement this result, we also give simple distributed constructions in both the LOCAL and CONGEST models.

It was recently found that there are very close connections between the existence of additive spanners (subgraphs where all distances are preserved up to an additive stretch), distance preservers (subgraphs in which demand pairs have their distance preserved exactly), and pairwise spanners (subgraphs in which demand pairs have their distance preserved up to a multiplicative or additive stretch) [Abboud-Bodwin SODA’16 8 J.ACM’17, Bodwin-Williams SODA’16]. We study these problems from an optimization point of view, where rather than studying the existence of extremal instances, we are given an instance and are asked to find the sparsest possible spanner/preserver. We give an O ( n 3/5 + ε )-approximation for distance preservers and pairwise spanners (for arbitrary constant ε > 0). This is the first nontrivial upper bound for either problem, both of which are known to be as hard to approximate as Label Cover. We also prove Label Cover hardness for approximating additive spanners, even for the cases of additive 1 stretch (where one might expect a polylogarithmic approximation, since the related multiplicative 2-spanner problem admits an O (log n )-approximation) and additive polylogarithmic stretch (where the related multiplicative spanner problem has an O (1)-approximation). Interestingly, the techniques we use in our approximation algorithm extend beyond distance-based problem to pure connectivity network design problems. In particular, our techniques allow us to give an O ( n 3/5 + ε )-approximation for the Directed Steiner Forest problem (for arbitrary constant ε > 0) when all edges have uniform costs, improving the previous best O ( n 2/3 + ε )-approximation due to Berman et al. [ICALP’11] (which holds for general edge costs).

A $t$-spanner of a graph $G$ is a subgraph $H$ in which all distances are preserved up to a multiplicative $t$ factor. A classical result of Althöfer et al. is that for every integer $k$ and every graph $G$, there is a $(2k-1)$-spanner of $G$ with at most $O(n^{1+1/k})$ edges. But for some settings the more interesting notion is not the number of edges, but the degrees of the nodes. This spurred interest in and study of spanners with small maximum degree. However, this is not necessarily a robust enough objective: we would like spanners that not only have small maximum degree, but also have "few" nodes of "large" degree. To interpolate between these two extremes, in this paper we initiate the study of graph spanners with respect to the $\ell_p$-norm of their degree vector, thus simultaneously modeling the number of edges (the $\ell_1$-norm) and the maximum degree (the $\ell_{\infty}$-norm). We give precise upper bounds for all ranges of $p$ and stretch $t$: we prove that the greedy $(2k-1)$-spanner has $\ell_p$ norm of at most $\max(O(n), O(n^{(k+p)/(kp)}))$, and that this bound is tight (assuming the Erdős girth conjecture). We also study universal lower bounds, allowing us to give "generic" guarantees on the approximation ratio of the greedy algorithm which generalize and interpolate between the known approximations for the $\ell_1$ and $\ell_{\infty}$ norm. Finally, we show that at least in some situations, the $\ell_p$ norm behaves fundamentally differently from $\ell_1$ or $\ell_{\infty}$: there are regimes ($p=2$ and stretch $3$ in particular) where the greedy spanner has a provably superior approximation to the generic guarantee.

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.

The minimum degree spanning tree (MDST) problem requires the construction of a spanning tree T for graph G, such that the maximum degree of T is the smallest among all spanning trees of G. Let d be this MDST degree for a given graph. In this paper, we present a randomized distributed approximation algorithm for the MDST problem that constructs a spanning tree with maximum degree in O(d+log n ). With high probability in n, the algorithm runs in O((D + √n) log4 n) rounds, in the broadcast-CONGEST model, where D is the graph diameter and n is the graph size. We then show how to derandomize this algorithm, obtaining the same asymptotic guarantees on degree and time complexity, but now requiring the standard CONGEST model. Although efficient approximation algorithms for the MDST problem have been known in the sequential setting since the 1990's (finding an exact solution is NP-hard), our algorithms are the first efficient distributed solutions. We conclude by proving a lower bound that establishes that any randomized MDST algorithm that guarantees a maximum degree in ∼Ω (d) requires &Ø#8764;Ω (n1/3) rounds, and any deterministic solution requires ∼Ω (n1/2) rounds. These bounds proves our deterministic algorithm to be asymptotically optimal, and eliminates the possibility of significantly more efficient randomized solutions.

We study three capacity problems in the mobile telephone model, a network abstraction that models the peer-to-peer communication capabilities implemented in most commodity smartphone operating systems. The capacity of a network expresses how much sustained throughput can be maintained for a set of communication demands, and is therefore a fundamental bound on the usefulness of a network. Because of this importance, wireless network capacity has been active area of research for the last two decades. The three capacity problems that we study differ in the structure of the communication demands. The first problem is pairwise capacity, where the demands are (source, destination) pairs. Pairwise capacity is one of the most classical definitions, as it was analyzed in the seminal paper of Gupta and Kumar on wireless network capacity. The second problem we study is broadcast capacity, in which a single source must deliver packets to all other nodes in the network. Finally, we turn our attention to all-to-all capacity, in which all nodes must deliver packets to all other nodes. In all three of these problems we characterize the optimal achievable throughput for any given network, and design algorithms which asymptotically match this performance. We also study these problems in networks generated randomly by a process introduced by Gupta and Kumar, and fully characterize their achievable throughput. Interestingly, the techniques that we develop for all-to-all capacity also allow us to design a one-shot gossip algorithm that runs within a polylogarithmic factor of optimal in every graph. This largely resolves an open question from previous work on the one-shot gossip problem in this model.

Data structures that allow efficient distance estimation have been extensively studied both in centralized models and classical distributed models. 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. 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 is 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.

We revisit the classical question of the relationship between the diameter of a graph and its expansion properties. One direction is well understood: expander graphs exhibit essentially the lowest possible diameter. We focus on the reverse direction, showing that "sufficiently large" graphs of fixed diameter and degree must be "good" expanders. We prove this statement for various definitions of "sufficiently large" (multiplicative/additive factor from the largest possible size), for different forms of expansion (edge, vertex, and spectral expansion), and for both directed and undirected graphs. A recurring theme is that the lower the diameter of the graph and (more importantly) the larger its size, the better the expansion guarantees. Aside from inherent theoretical interest, our motivation stems from the domain of network design. Both low-diameter networks and expanders are prominent approaches to designing high-performance networks in parallel computing, HPC, datacenter networking, and beyond. Our results establish that these two approaches are, in fact, inextricably intertwined. We leave the reader with many intriguing questions for future research.

We consider the Shallow-Light Steiner Network problem from a fixed-parameter perspective. Given a graph $G$, a distance bound $L$, and $p$ pairs of vertices $(s_1,t_1),\cdots,(s_p,t_p)$, the objective is to find a minimum-cost subgraph $G'$ such that $s_i$ and $t_i$ have distance at most $L$ in $G'$ (for every $i \in [p]$). Our main result is on the fixed-parameter tractability of this problem with parameter $p$. We exactly characterize the demand structures that make the problem "easy", and give FPT algorithms for those cases. In all other cases, we show that the problem is W$[1]$-hard. We also extend our results to handle general edge lengths and costs, precisely characterizing which demands allow for good FPT approximation algorithms and which demands remain W$[1]$-hard even to approximate.

We consider the Shallow-Light Steiner Network problem from a fixed-parameter perspective. Given a graph G, a distance bound L, and p pairs of vertices {(s_i,t_i)}_{i in [p]}, the objective is to find a minimum-cost subgraph G' such that s_i and t_i have distance at most L in G' (for every i in [p]). Our main result is on the fixed-parameter tractability of this problem for parameter p. We exactly characterize the demand structures that make the problem "easy", and give FPT algorithms for those cases. In all other cases, we show that the problem is W[1]-hard. We also extend our results to handle general edge lengths and costs, precisely characterizing which demands allow for good FPT approximation algorithms and which demands remain W[1]-hard even to approximate.

The notion of policy regret'' in online learning is supposed to capture the reactions of the adversary to the actions taken by the learner, which more traditional notions such as external regret do not take into account. We revisit this notion of policy regret, and first show that there are online learning settings in which policy regret and external regret are incompatible: any sequence of play which does well with respect to one must do poorly with respect to the other. We then focus on the game theoretic setting, when the adversary is a self-interested agent. In this setting we show that the external regret and policy regret are not in conflict, and in fact that a wide class of algorithms can ensure both as long as the adversary is also using such an algorithm. We also define a new notion of equilibrium which we call apolicy equilibrium'', and show that no-policy regret algorithms will have play which converges to such an equilibrium. Relating this back to external regret, we show that coarse correlated equilibria (which no-external regret players will converge to) are a strict subset of policy equilibria. So in game-theoretic settings every sequence of play with no external regret also has no policy regret, but the converse is not true.

A k-spanner of a graph G is a sparse subgraph H whose shortest path distances match those of G up to a multiplicative error k. In this paper we study spanners that are resistant to faults. A subgraph H ⊆ G is an f vertex fault tolerant (VFT) k-spanner if H \ F is a k-spanner of G \ F for any small set F of f vertices that might “fail.” One of the main questions in the area is: what is the minimum size of an f fault tolerant k-spanner that holds for all n node graphs (as a function of f, k and n)? This question was first studied in the context of geometric graphs [Levcopoulos et al. STOC ’98, Czumaj and Zhao SoCG ’03] and has more recently been considered in general undirected graphs [Chechik et al. STOC ’09, Dinitz and Krauthgamer PODC ’11]. In this paper, we settle the question of the optimal size of a VFT spanner, in the setting where the stretch factor k is fixed. Specifically, we prove that every (undirected, possibly weighted) n-node graph G has a (2k – 1)-spanner resilient to f vertex faults with Ok (f1–1/kn1+1/k) edges, and this is fully optimal (unless the famous Erdös Girth Conjecture is false). Our lower bound even generalizes to imply that no data structure capable of approximating distG\F (s, t) similarly can beat the space usage of our spanner in the worst case. To the best of our knowledge, this is the first instance in fault tolerant network design in which introducing fault tolerance to the structure increases the size of the (non-FT) structure by a sublinear factor in f. Another advantage of this result is that our spanners are constructed by a very natural and simple greedy algorithm, which is the obvious extension of the standard greedy algorithm used to build spanners in the non-faulty setting. We also consider the edge fault tolerant (EFT) model, defined analogously with edge failures rather than vertex failures. We show that the same spanner upper bound applies in this setting. Our data structure lower bound extends to the case k = 2 (and hence we close the EFT problem for 3-approximations), but it falls to D(f 1/2-1/(2k) · n1+1/k) for k > 3. We leave it as an open problem to close this gap.

The densest $k$-subgraph (D$k$S) problem and its corresponding minimization problem smallest $p$-edge subgraph (S$p$ES) have come to play a central role in approximation algorithms. This is due both to their practical importance and to their usefulness as a tool for solving and establishing approximation bounds for other problems. These two problems are not well understood, and it is widely believed that they do not admit a subpolynomial approximation ratio (although the best-known hardness results do not rule this out). In this paper we generalize both D$k$S and S$p$ES from graphs to hypergraphs. We consider the densest $k$-subhypergraph (D$k$SH) problem (given a hypergraph $(V, E)$, find a subset $W\subseteq V$ of $k$ vertices so as to maximize the number of hyperedges contained in $W$), and define the minimum $p$-union (M$p$U) problem (given a hypergraph, choose $p$ of the hyperedges so as to minimize the number of vertices in their union). We focus in particular on the case where all hyperedges have size 3, as this is the simplest nongraph setting. For this case we provide an $O(n^{4(4-\sqrt{3})/13 + \epsilon}) < O(n^{0.697831+\epsilon})$-approximation (for arbitrary constant $\epsilon > 0$) for D$k$SH and an $\tilde{O}(n^{2/5})$-approximation for M$p$U. We also give an $O(\sqrt{m})$-approximation for M$p$U in general hypergraphs. Finally, we examine the interesting special case of interval hypergraphs (instances where the vertices are a subset of the natural numbers and the hyperedges are intervals of the line) and prove that both problems admit an exact polynomial-time solution on these instances.

Emerging applications such as remote manipulation and remote robotic surgery require communication that is both timely and reliable, but the Internet natively supports only communication that is either completely reliable with no timeliness guarantees (e.g. TCP) or timely with best-effort reliability (e.g. UDP). We present an overlay transport service that can provide highly reliable communication while meeting stringent timeliness guarantees (e.g. 130ms round-trip latency across the US) over the Internet. To enable routing schemes that can support the necessary timeliness and reliability, we introduce dissemination graphs, providing a unified framework for specifying routing schemes ranging from a single path, to multiple disjoint paths, to arbitrary graphs. We conduct an extensive analysis of real-world network data, finding that a routing approach using two disjoint paths performs well in most cases, and that cases where two disjoint paths do not perform well typically involve problems around a source or destination. Based on this analysis, we develop a timely dissemination-graph-based routing method that can add targeted redundancy in problematic areas of the network. This approach can cover over 99% of the performance gap between a traditional single-path approach and an optimal (but prohibitively expensive) scheme, while two dynamic disjoint paths cover about 70% of this gap, and two static disjoint paths cover about 45%. This performance improvement is obtained at a cost increase of about 2% over two disjoint paths.

Load balancing is an important activity in distributed systems. At a high-level of abstraction, this problem assumes processes in the system begin with a potentially uneven assignment of “work” which they must then attempt to spread evenly. There are many different approaches to solving this problem. In this paper, we focus on local load balancing-an approach in which work is balanced in an iterative and distributed manner by having processes exchange work in each round with neighbors in an underlying communication network. The goal with local load balancing is to prove that these local exchanges will lead over time to a global balance. We describe and analyze a new local load balancing strategy called max neighbor, and prove a bound on the number of rounds required for it to obtain a parameterized level of balance, with high probability, in a general dynamic network topology. We then prove this analysis tight (within logarithmic factors) by describing a network and initial work distribution for which max neighbor matches its upper bound, and then build on this to prove that no load balancing algorithm in which every node exchanges work with at most one partner per round can converge asymptotically faster than max neighbor.

Given a finite metric space (V,d), an approximate distance oracle is a data structure which, when queried on two points u,v \in V, returns an approximation to the the actual distance between u and v which is within some bounded stretch factor of the true distance. There has been significant work on the tradeoff between the important parameters of approximate distance oracles (and in particular between the size, stretch, and query time), but in this paper we take a different point of view, that of per-instance optimization. If we are given an particular input metric space and stretch bound, can we find the smallest possible approximate distance oracle for that particular input? Since this question is not even well-defined, we restrict our attention to well-known classes of approximate distance oracles, and study whether we can optimize over those classes. In particular, we give an O(\log n)-approximation to the problem of finding the smallest stretch 3 Thorup-Zwick distance oracle, as well as the problem of finding the smallest P\v{a}tra\c{s}cu-Roditty distance oracle. We also prove a matching \Omega(\log n) lower bound for both problems, and an \Omega(n^{\frac{1}{k}-\frac{1}{2^{k-1}}}) integrality gap for the more general stretch (2k-1) Thorup-Zwick distance oracle. We also consider the problem of approximating the best TZ or PR approximate distance oracle with outliers, and show that more advanced techniques (SDP relaxations in particular) allow us to optimize even in the presence of outliers.

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 programs 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/ε) log n) rounds in the LOCAL model and with high probability finds a (1+ε)-approximation to the optimal LP solution for any 0 < ε ≤ 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.

It was recently found that there are very close connectionsbetween the existence of additive spanners (subgraphs where all distances are preserved up to an additive stretch), distance preservers (subgraphs in which demand pairs have their distance preserved exactly), and pairwise spanners (subgraphs in which demand pairs have their distance preserved up to a multiplicative or additive stretch) [Abboud-Bodwin SODA ‘16, Bodwin-Williams SODA ‘16]. We study these problemsfrom an optimization point of view, where ratherthan studying the existence of extremal instances we are given an instance and are asked to find the sparsest possible spanner/preserver. We give an O(n3/5+∊)-approximation for distance preservers and pairwisespanners (for arbitrary constant ∊ > 0). This is the first nontrivial upper bound for either problem, both of which are known to be as hard to approximate as Label Cover. We also prove Label Cover hardness for approximating additive spanners, even for the cases of additive 1 stretch (where one might expect a polylogarithmic approximation, since the related multiplicative 2-spanner problem admits an O(logn)-approximation) and additive polylogarithmic stretch (where the related multiplicative spanner problem has an O(1)-approximation). Interestingly, the techniques we use in our approximation algorithm extend beyond distance-based problem to pure connectivity network design problems. In particular, our techniques allow us to give an O(n3/5+∊)- approximation for the Directed Steiner Forest problem (for arbitrary constant ∊ > 0) when all edges have uniform costs, improving the previous best O(n2/3+∊)- approximation due to Berman et al. [ICALP ‘11] (whichholds for general edge costs).

In the Minimum k-Union problem (MkU) we are given a set system with n sets and are asked to select k sets in order to minimize the size of their union. Despite being a very natural problem, it has received surprisingly little attention: the only known approximation algorithm is an due to [Chlamtac et al APPROX’16]. This problem can also be viewed as the bipartite version of the Small Set Vertex Expansion problem (SSVE), which we call the Small Set Bipartite Vertex Expansion problem (SSBVE). SSVE, in which we are asked to find a set of k nodes to minimize their vertex expansion, has not been as well studied as its edge-based counterpart Small Set Expansion (SSE), but has recently received significant attention, e.g. [Louis-Makarychev APPROX ‘15]. However, due to the connection to Unique Games and hardness of approximation the focus has mostly been on sets of size k = Ω(n), while we focus on the case of general k, for which no polylogarithmic approximation is known. We improve the upper bound for this problem by giving an η1/4+∊ approximation for SSBVE for any constant ∊ > 0. Our algorithm follows in the footsteps of Densest k-Subgraph (DkS) and related problems, by designing a tight algorithm for random models, and then extending it to give the same guarantee for arbitrary instances. Moreover, we show that this is tight under plausible complexity conjectures: it cannot be approximated better than O(n1/4) assuming an extension of the so-called “Dense versus Random” conjecture for DkS to hypergraphs. In addition to conjectured hardness via our reduction, we show that the same lower bound is also matched by an integrality gap for a super-constant number of rounds of the Sherali-Adams LP hierarchy, and an even worse integrality gap for the natural SDP relaxation. Finally, we note that there exists a simple bicriteria approximation for the more general SSVE problem (where no non-trivial approximations were known for general k).

In the Steiner k -Forest problem, we are given an edge weighted graph, a collection D of node pairs, and an integer k ⩽ | D |. The goal is to find a min-weight subgraph that connects at least k pairs. The best known ratio for this problem is min { O (√ n ), O (√ k )} [Gupta et al. 2010]. In Gupta et al. [2010], it is also shown that ratio ρ for Steiner k -Forest implies ratio O (ρ · log 2 n ) for the related Dial-a-Ride problem. The only other algorithm known for Dial-a-Ride, besides the one resulting from Gupta et al. [2010], has ratio O (√ n ) [Charikar and Raghavachari 1998]. We obtain approximation ratio n 0.448 for Steiner k -Forest and Dial-a-Ride with unit weights, breaking the O (√ n ) approximation barrier for this natural case. We also show that if the maximum edge-weight is O ( n ϵ ), then one can achieve ratio O ( n (1 + ϵ) · 0.448 ), which is less than √ n if ϵ is small enough. The improvement for Dial-a-Ride is the first progress for this problem in 15 years. To prove our main result, we consider the following generalization of the Minimum k -Edge Subgraph (M k -ES) problem, which we call Min-Cost ℓ-Edge-Profit Subgraph (MCℓ-EPS): Given a graph G = ( V , E ) with edge-profits p = { p e : e ∈ E } and node-costs c = { c v : v ∈ V }, and a lower profit bound ℓ, find a minimum node-cost subgraph of G of edge-profit at least ℓ. The M k -ES problem is a special case of MCℓ-EPS with unit node costs and unit edge profits. The currently best known ratio for M k -ES is n 3-2√2 + ϵ [Chlamtac et al. 2012]. We extend this ratio to MCℓ-EPS for general node costs and profits bounded by a polynomial in n , which may be of independent interest.

We give an algorithm for computing approximate PSD factorizations of nonnegative matrices. The running time of the algorithm is polynomial in the dimensions of the input matrix, but exponential in the PSD rank and the approximation error. The main ingredient is an exact factorization algorithm when the rows and columns of the factors are constrained to lie in a general polyhedron. This strictly generalizes nonnegative matrix factorizations which can be captured by letting this polyhedron to be the nonnegative orthant.

Despite extensive efforts to meet ever-growing demands, today's datacenters often exhibit far-from-optimal performance in terms of network utilization, resiliency to failures, cost efficiency, incremental expandability, and more. Consequently, many novel architectures for high-performance datacenters have been proposed. We show that the benefits of state-of-the-art proposals are, in fact, derived from the fact that they are (implicitly) utilizing "expander graphs" (aka expanders) as their network topologies, thus unveiling a unifying theme of these proposals. We observe, however, that these proposals are not optimal with respect to performance, do not scale, or suffer from seemingly insurmountable deployment challenges. We leverage these insights to present Xpander, a novel datacenter architecture that achieves near-optimal performance and provides a tangible alternative to existing datacenter designs. Xpander's design turns ideas from the rich graph-theoretic literature on constructing optimal expanders into an operational reality. We evaluate Xpander via theoretical analyses, extensive simulations, experiments with a network emulator, and an implementation on an SDN-capable network testbed. Our results demonstrate that Xpander significantly outperforms both traditional and proposed datacenter designs. We discuss challenges to real-world deployment and explain how these can be resolved.

Despite significant recent progress on approximating graph spanners (subgraphs which approximately preserve distances), there are still several large gaps in our understanding. We give new results for two of them: approximating basic k-spanner (particularly for small k), and the dependence on f when approximating f-fault tolerant spanners. We first design an Õ(n1/3)-approximation for 4-spanner (both basic and directed). This was the last value of k for which only an -approximation was known for basic k-spanner, and thus implies that for any k the approximation ratio is at most Õ(n1/3). For basic k-spanner, we also show an integrality gap for the natural flow-based LP (the main tool in almost all nontrivial spanner approximations) which nearly matches the trivial approximation of . For f-fault tolerant spanners, we show that in the small-stretch setting (k ∊ {3, 4}) it is possible to entirely remove the dependence on f from the approximation ratio, at the cost of moving to bicriteria guarantees. The previous best dependence on f was either almost-linear (in the undirected setting) or exponential (in the directed setting for stretch 4).

We study the well-known Label Cover problem under the additional requirement that problem instances have large girth. We show that if the girth is some k , the problem is roughly 2 log 1-ϵ n)/k hard to approximate for all constant ϵ > 0. A similar theorem was claimed by Elkin and Peleg [2000] as part of an attempt to prove hardness for the basic k -spanner problem, but their proof was later found to have a fundamental error. Thus, we give both the first nontrivial lower bound for the problem of Label Cover with large girth as well as the first full proof of strong hardness for the basic k -spanner problem, which is both the simplest problem in graph spanners and one of the few for which super-logarithmic hardness was not known. Assuming NP ⊆ BPTIME (2 polylog(n) , we show (roughly) that for every k ⩾ 3 and every constant ϵ > 0, it is hard to approximate the basic k -spanner problem within a factor better than 2 log 1-ϵ n)/k . This improves over the previous best lower bound of only Ω(log n )/ k from Kortsarz [2001]. Our main technique is subsampling the edges of 2-query probabilistically checkable proofs (PCPs), which allows us to reduce the degree of a PCP to be essentially equal to the soundness desired. This turns out to be enough to basically guarantee large girth.

We study resistance sparsification of graphs, in which the goal is to find a sparse subgraph (with reweighted edges) that approximately preserves the effective resistances between every pair of nodes. We show that every dense regular expander admits a (1+epsilon)-resistance sparsifier of size ~O(n/epsilon), and conjecture this bound holds for all graphs on n nodes. In comparison, spectral sparsification is a strictly stronger notion and requires Omega(n/epsilon^2) edges even on the complete graph. Our approach leads to the following structural question on graphs: Does every dense regular expander contain a sparse regular expander as a subgraph? Our main technical contribution, which may of independent interest, is a positive answer to this question in a certain setting of parameters. Combining this with a recent result of von Luxburg, Radl, and Hein (JMLR, 2014) leads to the aforementioned resistance sparsifiers.

Many architectures for high-performance datacenters have been proposed. Surprisingly, recent studies show that datacenter designs with random network topologies outperform more sophisticated designs, achieving near-optimal throughput and bisection bandwidth, high resiliency to failures, incremental expandability, high cost efficiency, and more. Unfortunately, the inherent unstructuredness and unpredictability of random designs pose serious, arguably insurmountable, obstacles to their adoption in practice. Can these guarantees be achieved by well-structured, deterministic datacenters? We provide a surprising affirmative answer. We show, through a combination of theoretical analyses, extensive simulations, and experiments with a network emulator, that any "expander" network topology (as indeed are random graphs) comes with these benefits. We leverage this insight to present Xpander, a novel deterministic datacenter architecture that achieves all of the above desiderata while providing a tangible alternative to existing datacenter designs. We discuss challenges en route to deploying Xpander (including physical layout, cabling costs and complexity, backwards compatibility) and explain how these can be resolved.

A k-spanner is a subgraph in which distances are approximately preserved, up to some given stretch factor k. We focus on the following problem: Given a graph and a value k, can we find a k-spanner that minimizes the maximum degree? While reasonably strong bounds are known for some spanner problems, they almost all involve minimizing the total number of edges. Switching the objective to the degree introduces significant new challenges, and currently the only known approximation bound is an O~(Delta^(3-2*sqrt(2)))-approximation for the special case when k = 2 [Chlamtac, Dinitz, Krauthgamer FOCS 2012] (where Delta is the maximum degree in the input graph). In this paper we give the first non-trivial algorithm and polynomial-factor hardness of approximation for the case of general k. Specifically, we give an LP-based O~(Delta^((1-1/k)^2) )-approximation and prove that it is hard to approximate the optimum to within Delta^Omega(1/k) when the graph is undirected, and to within Delta^Omega(1) when it is directed.

In the Steiner k-Forest problem we are given an edge weighted graph, a collection D of node pairs, and an integer k \leq |D|. The goal is to find a minimum cost subgraph that connects at least k pairs. The best known ratio for this problem is min{O(sqrt{n}),O(sqrt{k})} [Gupta et al., 2008]. In [Gupta et al., 2008] it is also shown that ratio rho for Steiner k-Forest implies ratio O(rho log^2 n) for the Dial-a-Ride problem: given an edge weighted graph and a set of items with a source and a destination each, find a minimum length tour to move each object from its source to destination, but carrying at most k objects at a time. The only other algorithm known for Dial-a-Ride, besides the one resulting from [Gupta et al., 2008], has ratio O(sqrt{n}) [Charikar and Raghavachari, 1998]. We obtain ratio n^{0.448} for Steiner k-Forest and Dial-a-Ride with unit weights, breaking the O(sqrt{n}) ratio barrier for this natural special case. We also show that if the maximum weight of an edge is O(n^{epsilon}), then one can achieve ratio O(n^{(1+epsilon) 0.448}), which is less than sqrt{n} if epsilon is small enough. To prove our main result we consider the following generalization of the Minimum k-Edge Subgraph (Mk-ES) problem, which we call Min-Cost l-Edge-Profit Subgraph (MCl-EPS): Given a graph G=(V,E) with edge-profits p={p_e: e in E} and node-costs c={c_v: v in V}, and a lower profit bound l, find a minimum node-cost subgraph of G of edge profit at least l. The Mk-ES problem is a special case of MCl-EPS with unit node costs and unit edge profits. The currently best known ratio for Mk-ES is n^{3-2*sqrt{2} + epsilon} (note that 3-2*sqrt{2} < 0.1716). We extend this ratio to MCl-EPS for arbitrary node weights and edge profits that are polynomial in n, which may be of independent interest.

In the matroid secretary problem we are given a stream of elements and asked to choose a set of elements that maximizes the total value of the set, subject to being an independent set of a matroid given in advance. The difficulty comes from the assumption that decisions are irrevocable: if we choose to accept an element when it is presented by the stream then we can never get rid of it, and if we choose not to accept it then we cannot later add it. Babaioff, Immorlica, and Kleinberg [SODA 2007] introduced this problem, gave O(1)-competitive algorithms for certain classes of matroids, and conjectured that every matroid admits an O(1)-competitive algorithm. However, most matroids that are known to admit an O(1)-competitive algorithm can be easily represented using graphs (e.g. graphic, cographic, and transversal matroids). In particular, there is very little known about F-representable matroids (the class of matroids that can be represented as elements of a vector space over a field F), which are one of the foundational types of matroids. Moreover, most of the known techniques are as dependent on graph theory as they are on matroid theory. We go beyond graphs by giving O(1)-competitive algorithms for regular matroids (the class of matroids that are representable over any field), and use techniques that are fundamentally matroid-theoretic rather than graph-theoretic. Our main technique is to leverage the seminal regular matroid decomposition theorem of Seymour, which gives a method for decomposing any regular matroid into matroids which are either graphic, cographic, or isomorphic to a simple 10-element matroid. We show how to combine in a black-box manner any algorithms for these basic classes into an algorithm for a given regular matroid, i.e. how to respect the decomposition. In fact, this allows us to generalize beyond regular matroids to any class of matroids that admits such a decomposition into classes for which we already have good algorithms. In particular, we give an O(1)-competitive algorithm for the class of max-flow min-cut matroids, which Seymour showed can be decomposed into regular matroids and copies of the Fano matroid.

The significant progressg in constructing graph spanners that are sparse (small number of edges) or light (low total weight) has skipped spanners that are everywhere-sparse (small maximum degree). This disparity is in line with other network design problems, where the maximum-degree objective has been a notorious technical challenge. Our main result is for the Lowest Degree $2$-Spanner (LD2S) problem, where the goal is to compute a 2-spanner of an input graph so as to minimize the maximum degree. We design a polynomial-time algorithm achieving approximation factor O(\Delta^{3-2\sqrt{2}}) \approx O(\Delta^{0.172}), where \Delta is the maximum degree of the input graph. The previous O(\Delta^{1/4}) -- approximation was proved nearly two decades ago by Kortsarz and Peleg [SODA 1994, SICOMP 1998]. Our main conceptual contribution is to establish a formal connection between LD2S and a variant of the Densest k-Sub graph (DkS) problem. Specifically, we design for both problems strong relaxations based on the Sherali-Adams linear programming (LP) hierarchy, and show that ``faithful'' randomized rounding of the DkS-variant can be used to round LD2S solutions. Our notion of faithfulness intuitively means that all vertices and edges are chosen with probability proportional to their LP value, but the precise formulation is more subtle. Unfortunately, the best algorithms known for DkS use the Lovasz-Schrijver LP hierarchy in a non-faithful way [Bhaskara, Charikar, Chlamtac, Feige, and Vijayaraghavan, STOC 2010]. Our main technical contribution is to overcome this shortcoming, while still matching the gap that arises in random graphs by planting a sub graph with same log-density.

Distance computation (e.g., computing shortest paths) is one of the most fundamental primitives used in communication networks. The cost of effectively and accurately computing pairwise network distances can become prohibitive in large-scale networks such as the Internet and Peer-to-Peer (P2P) networks. To negotiate the rising need for very efficient distance computation at scales never imagined before, approximation techniques for numerous variants of this question have recently received significant attention in the literature. Several different areas of theoretical research have emerged centered around this problem, such as metric embeddings, distance labelings, spanners, and distance oracles. The goal is to preprocess the graph and store a small amount of information such that whenever a query for any pairwise distance is issued, the distance can be well approximated (i.e., with small stretch) very quickly in an online fashion. Specifically, the pre-processing (usually) involves storing a small sketch with each node, such that at query time only the sketches of the concerned nodes need to be looked up to compute the approximate distance. Techniques derived from metric embeddings have been considered extensively by the networking community, usually under the name of network coordinate systems. On the other hand, while the computation of distance oracles has received considerable attention in the context of web graphs and social networks, there has been little work towards similar algorithms within the networking community. In this paper, we present the first theoretical study of distance sketches derived from distance oracles in a distributed network. We first present a fast distributed algorithm for computing approximate distance sketches, based on a distributed implementation of the distance oracle scheme of [Thorup-Zwick, JACM 2005]. We also show how to modify this basic construction to achieve different tradeoffs between the number of pairs for which the distance estimate is accurate, the size of the sketches, and the time and message complexity necessary to compute them. These tradeoffs can then be combined to give an efficient construction of small sketches with provable average-case as well as worst-case performance. Our algorithms use only small-sized messages and hence are suitable for bandwidth-constrained networks, and can be used in various networking applications such as topology discovery and construction, token management, load balancing, monitoring overlays, and several other problems in distributed algorithms.

A natural requirement for many distributed structures is fault-tolerance: after some failures in the underlying network, whatever remains from the structure should still be effective for whatever remains from the network. In this paper we examine spanners of general graphs that are tolerant to vertex failures, and significantly improve their dependence on the number of faults r for all stretch bounds.

We examine directed spanners through flow-based linear programming relaxations. We design an ~O(n2/3)-approximation algorithm for the directed k-spanner problem that works for all k ≥ 1, which is the first sublinear approximation for arbitrary edge-lengths. Even in the more restricted setting of unit edge-lengths, our algorithm improves over the previous ~O(n1-1/k) approximation [BGJRW09] when k ≥ 4. For the special case of k=3 we design a different algorithm achieving an ~O(√n)-approximation, improving the previous ~O(n2/3) [EP05,BGJRW09] (independently of our work, an ~O(n1-1/⌈ k/2⌉) was recently devised [BRR10]). Both of our algorithms easily extend to the fault-tolerant setting, which has recently attracted attention but not from an approximation viewpoint. We also prove a nearly matching integrality gap of ~Ω(n1/3 - ε) for every constant ε > 0. A virtue of all our algorithms is that they are relatively simple. Technically, we introduce a new yet natural flow-based relaxation, and show how to approximately solve it even when its size is not polynomial. The main challenge is to design a rounding scheme that "coordinates" the choices of flow-paths between the many demand pairs while using few edges overall. We achieve this, roughly speaking, by randomization at the level of vertices.

In this paper we consider the problem of maximizing wireless network capacity (a.k.a. one-shot scheduling) in both the protocol and physical models. We give the first distributed algorithms with provable guarantees in the physical model, and show how they can be generalized to more complicated metrics and settings in which the physical assumptions are slightly violated. We also give the first algorithms in the protocol model that do not assume transmitters can coordinate with their neighbors in the interference graph, so every transmitter chooses whether to broadcast based purely on local events. Our techniques draw heavily from algorithmic game theory and machine learning theory, even though our goal is a distributed algorithm. Indeed, our main results allow every transmitter to run any algorithm it wants, so long as its algorithm has a learning-theoretic property known as no-regret in a game-theoretic setting.

In this paper we consider the problem of maximizing the number of supported connections in arbitrary wireless networks where a transmission is supported if and only if the signal-to-interference-plus-noise ratio at the receiver is greater than some threshold. The aim is to choose transmission powers for each connection so as to maximize the number of connections for which this threshold is met. We believe that analyzing this problem is important both in its own right and also because it arises as a subproblem in many other areas of wireless networking. We study both the complexity of the problem and also present some game theoretic results regarding capacity that is achieved by completely distributed algorithms. We also feel that this problem is intriguing since it involves both continuous aspects (i.e. choosing the transmission powers) as well as discrete aspects (i.e. which connections should be supported). Our results are: ldr We show that maximizing the number of supported connections is NP-hard, even when there is no background noise. This is in contrast to the problem of determining whether or not a given set of connections is feasible since that problem can be solved via linear programming. ldr We present a number of approximation algorithms for the problem. All of these approximation algorithms run in polynomial time and have an approximation ratio that is independent of the number of connections. ldr We examine a completely distributed algorithm and analyze it as a game in which a connection receives a positive payoff if it is successful and a negative payoff if it is unsuccessful while transmitting with nonzero power. We show that in this game there is not necessarily a pure Nash equilibrium but if such an equilibrium does exist the corresponding price of anarchy is independent of the number of connections. We also show that a mixed Nash equilibrium corresponds to a probabilistic transmission strategy and in this case such an equilibrium always exists and has a price of anarchy that is independent of the number of connections. This work was supported by NSF contract CCF-0728980 and was performed while the second author was visiting Bell Labs in Summer, 2008.

In this paper we consider the problem of maximizing wireless network capacity (a.k.a. one-shot scheduling) in both the protocol and physical models. We give the first distributed algorithms with provable guarantees in the physical model, and also give the first algorithms in the protocol model that do not assume transmitters can coordinate with their neighbors in the interference graph, so every transmitter chooses whether to broadcast based purely on local events. Our techniques draw heavily from algorithmic game theory and machine learning theory, even though our goal is a distributed algorithm. Indeed, our main results allow every transmitter to run any algorithm it wants, so long as its algorithm has a learning-theoretic property known as no-regret in a game-theoretic setting.

The classical secretary problem studies the problem of selecting online an element (a “secretary”) with maximum value in a randomly ordered sequence. The difficulty lies in the fact that an element must be either selected or discarded upon its arrival, and this decision is irrevocable. Constant-competitive algorithms are known for the classical secretary problems (see, e.g., the survey of Freeman [7]) and several variants. We study the following two extensions of the secretary problem: In the discounted secretary problem, there is a time-dependent “discount” factor d(t), and the benefit derived from selecting an element/secretary e at time t is d(t)·v(e). For this problem with arbitrary (not necessarily decreasing) functions d(t), we show a constant-competitive algorithm when the expected optimum is known in advance. With no prior knowledge, we exhibit a lower bound of , and give a nearly-matching O (log n)-competitive algorithm. In the weighted secretary problem, up to K secretaries can be selected; when a secretary is selected (s)he must be irrevocably assigned to one of K positions, with position k having weight w(k), and assigning object/secretary e to position k has benefit w(k) · v(e). The goal is to select secretaries and assign them to positions to maximize Σe,k w(k) · v(e) · xek where xek is an indicator variable that secretary e is assigned position k. We give constant-competitive algorithms for this problem. Most of these results can also be extended to the matroid secretary case (Babaioff et al. [2]) for a large family of matroids with a constant-factor loss, and an O(log rank) loss for general matroids. These results are based on a reduction from various matroids to partition matroids which present a unified approach to many of the upper bounds of Babaioff et al. These problems have connections to online mechanism design (see, e.g., Hajiaghayi et al. [9]). All our algorithms are monotone, and hence lead to truthful mechanisms for the corresponding online auction problems.

In many network applications it would be useful for individual nodes to have knowledge of distances (e.g. latency or bandwidth) in the network. If every node stored all distances then it would take Ω(n2) space at every node, and furthermore when a new node joins it would have to send an Ω(n)-bit message to Ω(n) other nodes, for a total communication complexity of Ω(n2) per update. In this paper we consider a specific class of metrics, those obeying an ε-three point condition, and show that by embedding these metrics into ultrametrics we can use only O(n) space at every node, have amortized communication complexity of O(n4/3) (allowing nodes to join and leave the network), and still estimate distances up to a (1+ε)log n + 5-stretch factor.

Given a weighted graph G=(V,E), a compact routing scheme is a distributed algorithm for forwarding packets from any source to any destination. The fundamental tradeoff is between the space used at each node and the stretch of the total route, measured by the multiplicative factor between the actual distance traveled and the length of the shortest possible route. We extend the normal definition with a slack parameter ε, which allows us to ignore up to εn2 of the shortest pairwise routes and give a guarantee on the remaining ones. For constant ε we give constant stretch, polylogarithmic space schemes in the name-dependent model and in the designer-port name-independent model, and give a lower bound that proves that such schemes do not exist in the fixed-port name-independent model. In the name-dependent model we also give a gracefully degrading scheme which works simultaneously for all ε > 0 and guarantees constant average stretch with polylog space.

A tiling of a finite abelian group G is a pair $(V,A)$ of subsets of G such that 0 is in both V and A and every $g\in G$ can be uniquely written as $g=v+a$ with $v\in V$ and $a\in A$. Tilings are a special case of normed factorizations, a type of factorization by subsets that was introduced by Hajós [Casopsis Puest Path. Rys., 74, (1949), pp. 157-162]. A tiling is said to be full rank if both V and A generate G. Cohen, Litsyn, Vardy, and Zémor [SIAM J. Discrete Math., 9 (1996), pp. 393-412] proved that any tiling of $\Z_2^n$ can be decomposed into full rank and trivial tilings. We generalize this decomposition from $\Z_2^n$ to all finite abelian groups. We also show how to generate larger full rank tilings from smaller ones, and give two sufficient conditions for a group to admit a full rank tiling, showing that many groups do admit them. In particular, we prove that if $p\geq 5$ is a prime and $n\geq 4$, then $\Z_p^n$ admits a full rank tiling. This bound on n is tight for $5\leq p\leq 11$, and is conjectured to be tight for all primes p.