The online sorting problem is a natural online analog of classical sorting: n elements arrive one by one and must be placed irrevocably into an array of size n so as to minimize the sum of absolute differences between consecutive elements. Recent work by Aamand et al. [SODA 2023] and Abrahamsen et al. [ESA 2024] showed that the optimal competitive ratio for this problem is Θ(√n), even when randomization is allowed. Bertram [ESA 2025] extended this bound to the online traveling salesman problem (TSP), of which online sorting is a special case on the line metric. These polynomial bounds raise the question of whether additional information can lead to improved performance. In this paper, we initiate the study of online sorting and TSP in the framework of machine-learned predictions. We characterize the exact tradeoff between consistency and robustness for online sorting with predictions, and prove a surprising lower bound showing that robustness is not lossless in this setting. This phenomenon sets online sorting apart from most previously studied online problems with predictions. We extend our results to online TSP with predictions on general metric spaces, where the same consistency-robustness tradeoff persists. Finally, we present a sharp contrast in the case of online TSP on the uniform metric. While Abrahamsen et al. gave an O(log n)-competitive algorithm without predictions for the uniform metric, we show that predictions enable an algorithm that is simultaneously O(1)-consistent and O(log n)-robust. We further extend this result to the setting of multiple predictions.

In the online sorting problem, we have an array $A$ of $n$ cells, and receive a stream of $n$ items $x_1,\dots,x_n\in [0,1]$. When an item arrives, we need to immediately and irrevocably place it into an empty cell. The goal is to minimize the sum of absolute differences between adjacent items, which is called the \emph{cost} of the algorithm. It has been shown by Aamand, Abrahamsen, Beretta, and Kleist (SODA 2023) that when the stream $x_1,\dots,x_n$ is generated adversarially, the optimal cost bound for any deterministic algorithm is $Θ(\sqrt{n})$. In this paper, we study the stochastic version of online sorting, where the input items $x_1,\dots,x_n$ are sampled uniformly at random. Despite the intuition that the stochastic version should yield much better cost bounds, the previous best algorithm for stochastic online sorting by Abrahamsen, Bercea, Beretta, Klausen and Kozma (ESA 2024) only achieves $\tilde{O}(n^{1/4})$ cost, which seems far from optimal. We show that stochastic online sorting indeed allows for much more efficient algorithms, by presenting an algorithm that achieves expected cost $\log n\cdot 2^{O(\log^* n)}$. We also prove a cost lower bound of $Ω(\log n)$, thus show that our algorithm is nearly optimal.

The problem of minimizing the total flow time on a single machine is one of the few problems for which we can give an optimal online algorithm: just schedule the job with the shortest remaining processing time (SRPT). However, this requires knowledge of the true running time \(p_j\) of each job \(j\). Azar, Leonardi, and Touitou recently asked: what if we are given estimates \(\hat{p}_j\) for each job, such that the multiplicative error between \(p_j\) and \(\hat{p}_j\) (called the distortion) is at most \(\mu\)? It is easy to construct examples where no algorithm can be \(o(\mu)\) competitive; can we get \(O(\mu)\) competitiveness?

In the online sorting problem, a sequence of \(n\) numbers in \([0,1]\) (including \(\{0,1\}\)) have to be inserted in an array of size \(m \ge n\) so as to minimize the sum of absolute differences between pairs of numbers occupying consecutive non-empty cells. Previously, Aamand et al. (SODA~2023) gave a deterministic \(2^{\sqrt{\log n} \sqrt{\log\log n + \log(1/\varepsilon)}}\)-competitive algorithm when \(m = (1+\varepsilon)n\) for any \(\varepsilon \ge \Omega(\log n / n)\). They also showed a lower bound: with \(m = \gamma n\) space, the competitive ratio of any deterministic algorithm is at least \(1/\gamma \cdot \Omega(\log n / \log\log n)\). This left an exponential gap between the upper and lower bounds for the problem.

We give the first algorithms for fully dynamic set cover with non-trivial worst-case guarantees for both recourse and update time. Specifically, we achieve O(logn) recourse and f· log(n) update time in the worst-case, for both approximation regimes: O(logn) and O(f) approximation. Prior to our work, all results for this problem either settled for amortized bounds on recourse and update time, or obtained f· log(n) update time in the worst-case but at the cost of Ω(m) worst-case recourse. (Here, m, n, f respectively denote the number of sets, maximum number of elements, and maximum frequency.)

The goal in the stochastic vertex cover problem is to obtain an approximately minimum vertex cover for a graph G⋆ that is realized by sampling each edge independently with some probability p∈ (0, 1] in a base graph G = (V, E). The algorithm is given the base graph G and the probability p as inputs, but its only access to the realized graph G⋆ is through queries on individual edges in G that reveal the existence (or not) of the queried edge in G⋆. In this paper, we resolve the central open question for this problem: to find a (1+ε)-approximate vertex cover using only Oε(n/p) edge queries. Prior to our work, there were two incomparable state-of-the-art results for this problem: a (3/2+ε)-approximation using Oε(n/p) queries (Derakhshan, Durvasula, and Haghtalab, 2023) and a (1+ε)-approximation using Oε((n/p)· RS(n)) queries (Derakhshan, Saneian, and Xun, 2025), where RS(n) is known to be at least 2Ω(logn/loglogn) and could be as large as n/2Θ(log* n). Our improved upper bound of Oε(n/p) matches the known lower bound of Ω(n/p) for any constant-factor approximation algorithm for this problem (Behnezhad, Blum, and Derakhshan, 2022). A key tool in our result is a new concentration bound for the size of minimum vertex cover on random graphs, which might be of independent interest.

In a linear combinatorial optimization problem, we are given a family F ⊆ 2U of feasible subsets of a ground set U of n elements, and our goal is to find S* = argminS ∈ F ⟨ w,1S ⟩. Traditionally, we are either given the weight vector up-front, or else we are given a value oracle which allows us to evaluate w(S) := ⟨ w, 1S ⟩ for any S ∈ F. We consider the weaker and more robust comparison oracle, which for any two feasible sets S, T ∈ F, reveals only if w(S) is less than/equal to/greater than w(T). We ask: When can we find the optimal feasible set S* = argminS ∈ F w(S) using a small number of comparison queries? If so, when can we do this efficiently?

Given an undirected, weighted graph $G=(V, E, w)$, a Gomory-Hu tree or cut tree (Gomory and Hu, 1961) is a tree T over the vertex set V such that for every pair of vertices $s, t \in V$, the ($s, t$) min-cut in T is also an ($s, t$) min-cut in G and has the same value. In this article, we give the first deterministic almost-linear-time algorithm for constructing a Gomory-Hu tree. Our algorithm runs in $m^{1+o(1)}$-time, where m denotes the number of edges in the input graph G; this is clearly optimal up to the $m^{o(1)}$ term in the running time. Prior to our work, the best deterministic algorithm for this problem dated back to the original algorithm of Gomory and Hu that runs in $n m^{1+o(1)}$ time using current maxflow algorithms. In fact, our algorithm is also the first almost-linear-time deterministic algorithm for even simpler problems, such as finding the k-edge-connected components of a graph. Our new result hinges on two separate and novel components that each introduce a distinct set of de-randomization tools of independent interest: - a deterministic reduction from the all-pairs min-cuts problem to the single-source min-cuts problem incurring only sub-polynomial overhead, and - a deterministic almost-linear time algorithm for the singlesource min-cuts problem.

We give an algorithm for finding the arboricity of a weighted, undirected graph, defined as the minimum number of spanning forests that cover all edges of the graph, in $\sqrt{n} m^{1+o(1)}$ time. This improves on the previous best bound of $\tilde{O}(nm)$ for weighted graphs and $\tilde{O}\left(\mathrm{~m}^{3/2}\right)$ for unweighted graphs (Gabow 1995) for this problem. The running time of our algorithm is dominated by a logarithmic number of calls to a directed global minimum cut subroutine – if the running time of the latter problem improves to $m^{1+o(1)}$ (thereby matching the running time of maximum flow), the running time of our arboricity algorithm would improve further to $m^{1+o(1)}$. We also give a new algorithm for computing the entire cut hierarchy – laminar multiway cuts with minimum cut ratio in recursively defined induced subgraphs – in $m n^{1+o(1)}$ time. The cut hierarchy yields the ideal edge loads (Thorup 2001) in a fractional spanning tree packing of the graph which, we show, also corresponds to a max-entropy solution in the spanning tree polytope. For the cut hierarchy problem, the previous best bound was $\tilde{O}\left(n^{2} m\right)$ for weighted graphs and $\tilde{O}\left(n m^{3/2}\right)$ for unweighted graphs.

In this paper, we study the parameterized complexity of local search, whose goal is to find a good nearby solution from the given current solution. Formally, given an optimization problem where the goal is to find the largest feasible subset S of a universe U, the new input consists of a current solution P (not necessarily feasible) as well as an ordinary input for the problem. Given the existence of a feasible solution S^*, the goal is to find a feasible solution as good as S^* in parameterized time f(k)⋅n^O(1), where k denotes the distance |PΔ S^*|. This model generalizes numerous classical parameterized optimization problems whose parameter k is the minimum number of elements removed from U to make it feasible, which corresponds to the case P = U. We apply this model to widely studied Constraint Satisfaction Problems (CSPs), where U is the set of constraints, and a subset U' of constraints is feasible if there is an assignment to the variables satisfying all constraints in U'. We give a complete characterization of the parameterized complexity of all boolean-alphabet symmetric CSPs, where the predicate’s acceptance depends on the number of true literals.

In online allocation problems, an algorithm must choose from a set of options at each step, where each option incurs a set of costs/rewards associated with a set of $d$ agents. The goal is to minimize/maximize a function of the accumulated costs/rewards assigned to the agents over the course of the entire allocation process. Such problems are common in combinatorial optimization, including minimization problems such as machine scheduling and network routing, as well as maximization problems such as fair allocation for welfare maximization. In this paper, we develop a general learning-augmented algorithmic framework for online allocation problems that produces a nearly optimal solution using only a single $d$-dimensional vector of learned weights. Using this general framework, we derive learning-augmented online algorithms for a broad range of application problems in routing, scheduling, and fair allocation. Our main tool is convex programming duality, which may also have further implications for learning-augmented algorithms in the future.

The field of learning-augmented algorithms seeks to use ML techniques on past instances of a problem to inform an algorithm designed for a future instance. In this paper, we introduce a novel model for learning-augmented algorithms inspired by online learning. In this model, we are given a sequence of instances of a problem and the goal of the learning-augmented algorithm is to use prior instances to propose a solution to a future instance of the problem. The performance of the algorithm is measured by its average performance across all the instances, where the performance on a single instance is the ratio between the cost of the algorithm's solution and that of an optimal solution for that instance. We apply this framework to the classic $k$-median clustering problem, and give an efficient learning algorithm that can approximately match the average performance of the best fixed $k$-median solution in hindsight across all the instances. We also experimentally evaluate our algorithm and show that its empirical performance is close to optimal, and also that it automatically adapts the solution to a dynamically changing sequence.

Abstract It is natural to generalize the online $$k$$ k -Server problem by allowing each request to specify not only a point p, but also a subset S of servers that may serve it. To date, only a few special cases of this problem have been studied. The objective of the work presented in this paper has been to more systematically explore this generalization in the case of uniform and star metrics. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page p, but also a subset S of cache slots, and is satisfied by having a copy of p in some slot in S. We call this problem Slot-Heterogenous Paging. In realistic settings only certain subsets of cache slots or servers would appear in requests. Therefore we parameterize the problem by specifying a family $${\mathcal {S}}\subseteq 2^{[k]}$$ S ⊆ 2 [ k ] of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size k and family $${\mathcal {S}}$$ S : If all request sets are allowed ( $${\mathcal {S}}=2^{[k]}\setminus \{\emptyset \}$$ S = 2 [ k ] \ { ∅ } ), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging ( $${\mathcal {S}}=\{[k]\}$$ S = { [ k ] } ). As a function of $$|{\mathcal {S}}|$$ | S | and k, the optimal deterministic ratio is polynomial: at most $$O(k^2|{\mathcal {S}}|)$$ O ( k 2 | S | ) and at least $$\Omega (\sqrt{|{\mathcal {S}}|})$$ Ω ( | S | ) . For any laminar family $${\mathcal {S}}$$ S of height h, the optimal ratios are O(hk) (deterministic) and $$O(h^2\log k)$$ O ( h 2 log k ) (randomized). The special case of laminar $${\mathcal {S}}$$ S that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio for weighted All-or-One Paging is $$\Theta (k)$$ Θ ( k ) . Offline All-or-One Paging is

The vertex connectivity of an m -edge n -vertex undirected graph is the smallest number of vertices whose removal disconnects the graph or leaves only a singleton vertex. In 1974, Aho Hopcroft and Ullman asked if vertex connectivity can be computed in linear time. Despite the substantial effort in the past five decades, the best-known running time is \(\tilde{O}(mn)\) by Henzinger-Rao-Gabow (FOCS 1996). Indeed, no algorithm with an o ( mn ) running time is known even if we assume a linear-time max-flow algorithm. In this article, we give an affirmative answer to this long-standing open problem (up to a sub-polynomial factor). We present a randomized reduction from the vertex connectivity problem to the max-flow problem which incurs only a poly-logarithmic overhead in runtime. Using this reduction, we can solve vertex connectivity in almost linear time by using the celebrated almost-linear-time max-flow algorithms by Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva (FOCS 2022) and Brand-Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva-Sidford (FOCS 2023). Using our new techniques, we also obtain an algorithm for directed vertex connectivity with a running time of n 2 + o (1) time which improves the best-known bound of \(\tilde{O}(mn)\) by Henzinger-Rao-Gabow (FOCS 1996).

We give a deterministic algorithm for finding the minimum (weight) cut of an undirected graph on n vertices and m edges using polylog ( n ) calls to a black box maximum flow subroutine. Using the current best deterministic maximum flow algorithms, this marks the first improvement for this problem since a running time bound of \(\tilde{O}(mn)\) was established by several papers in the early 1990s. Our global minimum cut algorithm is obtained as a corollary of a deterministic minimum Steiner cut algorithm, where a minimum Steiner cut is a minimum (weight) set of edges whose removal disconnects at least one pair of vertices among a designated set of terminal vertices. We also give a remarkably simple randomized minimum Steiner cut algorithm that still improves the best known randomized algorithm for the problem. Our main technical contribution is a new tool that we call isolating cuts . Given a set of vertices R , this entails finding cuts of minimum weight that separate (or isolate) each individual vertex \(v\in R\) from the rest of the vertices \(R\setminus \lbrace v\rbrace\) . Naïvely, this can be done using |R| maximum flow calls, but we show that just O (log |R| ) calls on graphs containing O(n) vertices and O(m) edges suffice. We call this the isolating cut lemma .

In recent years, there has been a surge of interest in the use of machine-learned predictions to bypass worst-case lower bounds for classical problems in combinatorial optimization. So far, the focus has mostly been on online algorithms, where information-theoretic barriers are overcome using predictions about the unknown future. In this paper, we consider the complementary question of using learned information to overcome computational barriers in the form of approximation hardness of polynomial-time algorithms for NP-hard (offline) problems. We show that noisy predictions about the optimal solution can be used to break classical hardness results for maximization problems such as the max-cut problem and more generally, maximization versions of constraint satisfaction problems (CSPs).

Karger (STOC 1995) gave the first FPTAS for the network (un)reliability problem, setting in motion research over the next three decades that obtained increasingly faster running times, eventually leading to a Õ(n2)-time algorithm (Karger, STOC 2020). This represented a natural culmination of this line of work because the algorithmic techniques used can enumerate Θ(n2) (near)-minimum cuts. In this paper, we go beyond this quadratic barrier and obtain a faster FPTAS for the network unreliability problem. Our algorithm runs in m1+o(1) + Õ)(n1.5) time.

The online k-taxi problem generalizes the k-server problem, requiring servers to move between source-sink pairs in an n-point metric space, and the cost is the overhead incurred. In the deterministic setting, the problem has a lower bound on the competitiveness of Ω(2k), showing that it is significantly harder than k-server. Randomized algorithms are known with competitiveness O(2k log n) (by Coester and Koutsoupias), (by Buchbinder, Coester and Naor), where Δ is the aspect ratio of the n-point metric space), and O((n log k)2 log n) (by Bubeck, Buchbinder, Coester, and Sellke). The best lower bound known is Ω(log2 k) which is inherited from the k-server problem, obtained in a recent breakthrough by Bubeck, Coester, and Rabani, showing a large gap in our understanding of problems that go slightly beyond the metrical task system framework.

The hypergraph unreliability problem asks for the probability that a hypergraph gets disconnected when every hyperedge fails independently with a given probability. For graphs, the unreliability problem has been studied over many decades, and multiple fully polynomial-time approximation schemes are known starting with the work of Karger (STOC 1995). In contrast, prior to this work, no non-trivial result was known for hypergraphs (of arbitrary rank). In this paper, we give quasi-polynomial time approximation schemes for the hypergraph unreliability problem. For any fixed ε ∈ (0, 1), we first give a (1+ε)-approximation algorithm that runs in mO(logn) time on an m-hyperedge, n-vertex hypergraph. Then, we improve the running time to m· nO(log2 n) with an additional exponentially small additive term in the approximation.

A Gomory-Hu tree (also called a cut tree) succinctly represents $(s, t)$ min-cuts (and therefore, $(s, t)$ max-flow values) of all pairs of vertices $s, t$ in an undirected graph. In this paper, we give an $m^{1+o(1)}$-time algorithm for constructing a Gomory-Hu tree for a graph with m edges. This shows that the all-pairs max-flows problem has the same running time as the single-pair max-flow problem, up to a subpolynomial factor. Prior to our work, the best known Gomory-Hu tree algorithm was obtained in recent work by Abboud et al. (FOCS 2022) and requires $\tilde{O}\left(n^{2}\right)$ time for a graph with n vertices. Our result marks a natural culmination of over 60 years of research into the all-pairs maxflows problem that started with Gomory and Hu’s pathbreaking result introducing the Gomory-Hu tree in 1961.

Online allocation is a broad class of problems where items arriving online have to be allocated to agents who have a fixed utility/cost for each assigned item so to maximize/minimize some objective. This framework captures a broad range of fundamental problems such as the Santa Claus problem (maximizing minimum utility), Nash welfare maximization (maximizing geometric mean of utilities), makespan minimization (minimizing maximum cost), minimization of 𝓁_p-norms, and so on. We focus on divisible items (i.e., fractional allocations) in this paper. Even for divisible items, these problems are characterized by strong super-constant lower bounds in the classical worst-case online model. In this paper, we study online allocations in the learning-augmented setting, i.e., where the algorithm has access to some additional (machine-learned) information about the problem instance. We introduce a general algorithmic framework for learning-augmented online allocation that produces nearly optimal solutions for this broad range of maximization and minimization objectives using only a single learned parameter for every agent. As corollaries of our general framework, we improve prior results of Lattanzi et al. (SODA 2020) and Li and Xian (ICML 2021) for learning-augmented makespan minimization, and obtain the first learning-augmented nearly-optimal algorithms for the other objectives such as Santa Claus, Nash welfare, 𝓁_p-minimization, etc. We also give tight bounds on the resilience of our algorithms to errors in the learned parameters, and study the learnability of these parameters.

In recent years, there has been an increasing focus on designing online algorithms with (machine-learned) predictions. The ideal learning-augmented algorithm is comparable to the optimum when given perfect predictions (consistency), to the best online approximation for arbitrary predictions (robustness), and should interpolate between these extremes as a smooth function of the prediction error. In this paper, we quantify these guarantees in terms of a general property that we call discrete-smoothness, and achieve discrete-smooth algorithms for online covering, specifically the facility location and set cover problems. For set cover, our work improves the results of Bamas, Maggiori, and Svensson (2020) by augmenting consistency and robustness with smoothness guarantees. For facility location, our work improves on prior work by Almanza et al. (2021) by generalizing to nonuniform costs and also providing smoothness guarantees by augmenting consistency and robustness.

We introduce the notion of fair cuts as an approach to leverage approximate (s, t)-mincut (equivalently (s, t)-maxflow) algorithms in undirected graphs to obtain near-linear time approximation algorithms for several cut problems. Informally, for any α ≥ 1, an α-fair (s, t)-cut is an (s, t)-cut such that there exists an (s, t)-flow that uses 1/α fraction of the capacity of every edge in the cut. (So, any α-fair cut is also an α-approximate mincut, but not vice-versa.) We give an algorithm for (1 + ε)-fair (s, t)-cut in Õ(m)-time, thereby matching the best runtime for (1 + ε)-approximate (s, t)-mincut [Peng, SODA '16]. We then demonstrate the power of this approach by showing that this result almost immediately leads to several applications: • the first nearly-linear time (1 + ε)-approximation algorithm that computes all-pairs maxflow values (by constructing an approximate Gomory-Hu tree). Prior to our work, such a result was not known even for the special case of Steiner mincut [Dinitz and Vainstein, STOC '94; Cole and Hariharan, STOC '03]; • the first almost-linear-work subpolynomial-depth parallel algorithms for computing (1+ε)-approximations for all-pairs maxflow values (again via an approximate Gomory-Hu tree) in unweighted graphs; • the first near-linear time expander decomposition algorithm that works even when the expansion parameter is polynomially small; this subsumes previous incomparable algorithms [Nanongkai and Saranurak, FOCS '17; Wulff-Nilsen, FOCS '17; Saranurak and Wang, SODA '19]. * The full version of the paper can be accessed at https://arxiv.org/abs/2203.00751

We give an almost-linear time algorithm for the Steiner connectivity augmentation problem: given an undirected graph, find a smallest (or minimum weight) set of edges whose addition makes a given set of terminals τ-connected (for any given τ > 0). The running time of our algorithm is dominated by polylogarithmic calls to any maximum flow subroutine; using the recent almost-linear time maximum flow algorithm (Chen et al., FOCS 2022), we get an almost-linear running time for our algorithm as well. This is tight up to the polylogarithmic factor even for just two terminals. Prior to our work, an almost-linear (in fact, near-linear) running time was known only for the special case of global connectivity augmentation, i.e., when all vertices are terminals (Cen et al., STOC 2022). We also extend our algorithm to the closely related Steiner splitting-off problem, where the edges incident on a vertex have to be split-off while maintaining the (Steiner) connectivity of a given set of terminals. Prior to our work, a nearly-linear time algorithm was known only for the special case of global connectivity (Cen et al., STOC 2022). The only known generalization beyond global connectivity was to preserve all pairwise connectivities using a much slower algorithm that makes n calls to an all-pairs maximum flow (or Gomory-Hu tree) subroutine (Lau and Yung, SICOMP 2013), as against polylog(n) calls to a (single-pair) maximum flow subroutine in this work. * Ruoxu Cen and Debmalya Panigrahi were supported in part by NSF grants CCF-1750140 (CAREER Award) and CCF-1955703.

It is natural to generalize the online $k$-Server problem by allowing each request to specify not only a point $p$, but also a subset $S$ of servers that may serve it. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page $p$, but also a subset $S$ of cache slots, and is satisfied by having a copy of $p$ in some slot in $S$. We call this problem Slot-Heterogenous Paging. We parameterize the problem by specifying a family $\mathcal S \subseteq 2^{[k]}$ of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size $k$ and family $\mathcal S$: - If all request sets are allowed ($\mathcal S=2^{[k]}\setminus\{\emptyset\}$), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard \Paging ($\mathcal S=\{[k]\}$). - As a function of $|\mathcal S|$ and $k$, the optimal deterministic ratio is polynomial: at most $O(k^2|\mathcal S|)$ and at least $Ω(\sqrt{|\mathcal S|})$. - For any laminar family $\mathcal S$ of height $h$, the optimal ratios are $O(hk)$ (deterministic) and $O(h^2\log k)$ (randomized). - The special case of laminar $\mathcal S$ that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio for weighted All-or-One Paging is $Θ(k)$. Offline All-or-One Paging is NP-hard. Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set $\mathcal P of pages, and is satisfied by fetching any page from $\mathcal P into the cache. The optimal ratios for the latter problem (with laminar family of height $h$) are at most $hk$ (deterministic) and $h\,H_k$ (randomized).

On hypergraphs with m hyperedges and n vertices, where p denotes the total size of the hyperedges, we provide the following results: We give an algorithm that runs in \(\widetilde{O}(mn^{2k-2})\) time for finding a minimum k -cut in hypergraphs of arbitrary rank. This algorithm betters the previous best running time for the minimum k -cut problem, for k > 2. We give an algorithm that runs in \(\widetilde{O}(n^{\max \lbrace r,2k-2\rbrace })\) time for finding a minimum k -cut in hypergraphs of constant rank r . This algorithm betters the previous best running times for both the minimum cut and minimum k -cut problems for dense hypergraphs. Both of our algorithms are Monte Carlo, i.e., they return a minimum k -cut (or minimum cut) with high probability. These algorithms are obtained as instantiations of a generic branching randomized contraction technique on hypergraphs, which extends the celebrated work of Karger and Stein on recursive contractions in graphs. Our techniques and results also extend to the problems of minimum hedge-cut and minimum hedge- k -cut on hedgegraphs, which generalize hypergraphs.

Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret , defined as the maximum difference between the solution’s cost and that of an optimal solution in hindsight once the input has been realized. For graph problems in P , such as shortest path and minimum spanning tree, robust polynomial-time algorithms that obtain a constant approximation on regret are known. In this paper, we study robust algorithms for minimizing regret in NP -hard graph optimization problems, and give constant approximations on regret for the classical traveling salesman and Steiner tree problems.

This article presentsuniversalalgorithms for clustering problems, including the widely studiedk-median,k-means, andk-center objectives. The input is a metric space containing allpotentialclient locations. The algorithm must selectkcluster centers such that they are a good solution foranysubset of clients that actually realize. Specifically, we aim for lowregret, defined as the maximum over all subsets of the difference between the cost of the algorithm’s solution and that of an optimal solution. A universal algorithm’s solutionSolfor a clustering problem is said to be an α , β-approximation if for all subsets of clientsC′, it satisfiessol(C′) ≤ α ċopt(C′) + β ċmr, whereopt(C′ is the cost of the optimal solution for clients (C′) andmris the minimum regret achievable by any solution. Our main results are universal algorithms for the standard clustering objectives ofk-median,k-means, andk-center that achieve (O(1),O(1))-approximations. These results are obtained via a novel framework for universal algorithms using linear programming (LP) relaxations. These results generalize to other ℓp-objectives and the setting where some subset of the clients arefixed. We also give hardness results showing that (α, β)-approximation is NP-hard if α or β is at most a certain constant, even for the widely studied special case of Euclidean metric spaces. This shows that in some sense, (O(1),O(1))-approximation is the strongest type of guarantee obtainable for universal clustering.

We study the problem of learning influence adoption in networks. In this problem, a communicable entity (such as an infectious disease, a computer virus, or a social media meme) propagates through a network, and the goal is to learn the state of each individual node by sampling only a small number of nodes and observing/testing their states. We study this problem in heterogeneous networks, in which each individual node has a set of distinct features that determine how it is affected by the propagating entity. We give an efficient algorithm with nearly optimal sample complexity for two variants of this learning problem, corresponding to symptomatic and asymptomatic spread. In each case, the optimal sample complexity naturally generalizes the complexity of learning how nodes are affected in isolation, and the complexity of learning influence adoption in a homogeneous network.

In 1961, Gomory and Hu showed that the All-Pairs Max-Flow problem of computing the max-flow between all $\begin{pmatrix}n\\2\end{pmatrix}$ pairs of vertices in an undirected graph can be solved using only $n-1$ calls to any (single-pair) max-flow algorithm. Even assuming a linear-time max-flow algorithm, this yields a running time of $O(mn)$, which is $O(n^{3})$ when $m=\Theta(n^{2})$. While subsequent work has improved this bound for various special graph classes, no subcubic-time algorithm has been obtained in the last 60 years for general graphs. We break this longstanding barrier by giving an $\tilde{O}(n^{2})$-time algorithm on general, integer-weighted graphs. Combined with a popular complexity assumption, we establish a counter-intuitive separation: all-pairs max-flows are strictly easier to compute than all-pairs shortest-paths.Our algorithm produces a cut-equivalent tree, known as the Gomory-Hu tree, from which the max-flow value for any pair can be retrieved in near-constant time. For unweighted graphs, we refine our techniques further to produce a Gomory-Hu tree in the time of a poly-logarithmic number of calls to any maxflow algorithm. This shows an equivalence between the all-pairs and single-pair max-flow problems, and is optimal up to polylogarithmic factors. Using the recently announced $m^{1+o(1)}$-time max-flow algorithm (Chen et al., March 2022), our Gomory-Hu tree algorithm for unweighted graphs also runs in $m^{1+o(1)}$-time.

Many online trip planning and navigation software need to routinely solve the problem of deciding where to take stops during a journey for various services such as refueling (or EV charging), rest stops, food, etc. The goal is to minimize the overhead of these stops while ensuring that the traveller is not starved of any essential resource (such as fuel, rest, or food) during the journey. In this paper, we formally model this problem and call it the pit stop problem. We design algorithms for this problem under various settings: single vs multiple types of stops, and offline vs online optimization (i.e., in advance of or during the trip). Our algorithms achieve provable guarantees in terms of approximating the optimal solution. We then extensively evaluate our algorithms on real world data and demonstrate that they significantly outperform baseline solutions.

This paper studies online algorithms augmented with multiple machine-learned predictions. We give a generic algorithmic framework for online covering problems with multiple predictions that obtains an online solution that is competitive against the performance of the best solution obtained from the predictions. Our algorithm incorporates the use of predictions in the classic potential-based analysis of online algorithms. We apply our algorithmic framework to solve classical problems such as online set cover, (weighted) caching, and online facility location in the multiple predictions setting.

The growing body of work in learning-augmented online algorithms studies how online algorithms can be improved when given access to ML predictions about the future. Motivated by ML models that give a confidence parameter for their predictions, we study online algorithms with predictions that are $\epsilon$-accurate: namely, each prediction is correct with probability (at least) $\epsilon$, but can be arbitrarily inaccurate with the remaining probability. We show that even with predictions that are accurate with a small probability and arbitrarily inaccurate otherwise, we can dramatically outperform worst-case bounds for a range of classical online problems including caching, online set cover, and online facility location. Our main results are an $O(\log(1/\varepsilon))$-competitive algorithm for caching, and a simple $O(1/\varepsilon)$-competitive algorithm for a large family of covering problems, including set cover and facility location, with $\epsilon$-accurate predictions.

The Santa Claus problem is a fundamental problem in {\em fair division}: the goal is to partition a set of {\em heterogeneous} items among {\em heterogeneous} agents so as to maximize the minimum value of items received by any agent. In this paper, we study the online version of this problem where the items are not known in advance and have to be assigned to agents as they arrive over time. If the arrival order of items is arbitrary, then no good assignment rule exists in the worst case. However, we show that, if the arrival order is random, then for $n$ agents and any $\varepsilon > 0$, we can obtain a competitive ratio of $1-\varepsilon$ when the optimal assignment gives value at least $\Omega(\log n / \varepsilon^2)$ to every agent (assuming each item has at most unit value). We also show that this result is almost tight: namely, if the optimal solution has value at most $C \ln n / \varepsilon$ for some constant $C$, then there is no $(1-\varepsilon)$-competitive algorithm even for random arrival order.

This paper explores the use of machine learning for estimating the selectivity of range queries in database systems. Using classic learning theory for real-valued functions based on shattering dimension, we show that the selectivity function of a range space with bounded VC-dimension is learnable. As many popular classes of queries (e.g., orthogonal range search, inequalities involving linear combination of attributes, distance-based search, etc.) represent range spaces with finite VC-dimension, our result immediately implies that their selectivity functions are also learnable. To the best of our knowledge, this is the first attempt at formally explaining the role of machine learning techniques in selectivity estimation, and complements the growing literature in empirical studies in this direction. Supplementing these theoretical results, our experimental results demonstrate that, empirically, even a basic learning algorithm with generic models is able to produce accurate predictions across settings, matching state-of-art methods designed for specific queries, and using training sample sizes commensurate with our theory.

Online algorithms with predictions is a popular and elegant framework for bypassing pessimistic lower bounds in competitive analysis. In this model, online algorithms are supplied with future predictions and the goal is for the competitive ratio to smoothly interpolate between the best offline and online bounds as a function of the prediction error. In this paper, we study online graph problems with predictions. Our contributions are the following: The first question is defining prediction error. For graph/metric problems, there can be two types of error, locations that are not predicted, and locations that are predicted but the predicted and actual locations do not coincide exactly. We design a novel definition of prediction error called metric error with outliers to simultaneously capture both types of errors, which thereby generalizes previous definitions of error that only capture one of the two error types. We give a general framework for obtaining online algorithms with predictions that combines, in a “black box” fashion, existing online and offline algorithms, under certain technical conditions. To the best of our knowledge, this is the first general-purpose tool for obtaining online algorithms with predictions. Using our framework, we obtain tight bounds on the competitive ratio of several classical graph problems as a function of metric error with outliers: Steiner tree, Steiner forest, priority Steiner tree/forest, and uncapacitated/capacitated facility location. Both the definition of metric error with outliers and the general framework for combining offline and online algorithms are not specific to the problems that we consider in this paper. We hope that these will be useful for future work on other problems in this domain.

We give an algorithm for augmenting the edge connectivity of an undirected graph by using the isolating cuts framework (Li and Panigrahi, FOCS ‘20). Our algorithm uses poly-logarithmic calls to any max-flow algorithm, which yields a running time of Õ(m + n3/2) and improves on the previous best time of Õ(n2) (Benczúr and Karger, SODA ‘98) for this problem. We also obtain an identical improvement in the running time of the closely related edge splitting off problem in undirected graphs.

We give an Õ(m)-time algorithm for the edge connectivity augmentation problem and the closely related edge splitting-off problem. This is optimal up to lower order terms and closes the long line of work on these problems.

We consider two generalizations of the classical weighted paging problem that incorporate the notion of delayed service of page requests. The first is the (weighted) paging with time windows (\sf PageTW) problem, which is like the classical weighted paging problem except that each page request only needs to be served before a given deadline. This problem arises in many practical applications of online caching, such as the “deadline” I/O scheduler in the Linux kernel and video-on-demand streaming. The second, and more general, problem is the (weighted) paging with delay (\sf PageD) problem, where the delay in serving a page request results in a penalty being added to the objective. This problem generalizes the caching problem to allow delayed service, a line of work that has recently gained traction in online algorithms (e.g., [Y. Emek, S. Kutten, and R. Wattenhofer, Proceedings of the 48 th Annual ACM SIGACT Symposium on Theory of Computing, 2016, pp. 333--344; Y. Azar et al., Proceedings of the 49 th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 551--563; Y. Azar and N. Touitou, Proceedings of the 60 th IEEE Annual Symposium on Foundations of Computer Science, 2019, pp. 60--71]). We give $O(\log k\log n)$-competitive algorithms for both the \sf PageTW and \sf PageD problems on $n$ pages with a cache of size $k$. This significantly improves on the previous best bounds of $O(k)$ for both problems [Y. Azar et al., Proceedings of the 49 th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 551--563]. We also consider the offline \sf PageTW and \sf PageD problems, for which we give $O(1)$-approximation algorithms and prove APX-hardness. These are the first results for the offline problems; even NP-hardness was not known before our work. At the heart of our algorithms is a novel “hitting-set” LP relaxation of the \sf PageTW problem that overcomes the $\Omega(k)$ integrality gap of the natural LP for the problem. To the best of our knowledge, this is the first example of an LP-based algorithm for an online problem with delays/deadlines.

In this article, we initiate the study of the weighted paging problem with predictions. This continues the recent line of work in online algorithms with predictions, particularly that of Lykouris and Vassilvitski (ICML 2018) and Rohatgi (SODA 2020) on unweighted paging with predictions. We show that unlike unweighted paging, neither a fixed lookahead nor a knowledge of the next request for every page is sufficient information for an algorithm to overcome the existing lower bounds in weighted paging. However, a combination of the two, which we call strong per request prediction (SPRP), suffices to give a 2-competitive algorithm. We also explore the question of gracefully degrading algorithms with increasing prediction error, and give both upper and lower bounds for a set of natural measures of prediction error.

We study the$k$-server problem with time-windows. In this problem, each request$i$arrives at some point$v_{i}$of an$n$-point metric space at time$b_{i}$and comes with a deadline$e_{i}$. One of the$k$servers must be moved to$v_{i}$at some time in the interval [$b_{i}, e_{i}$] to satisfy this request. We give an online algorithm for this problem with a competitive ratio of$\text{poly}\log(n, \Delta)$, where$\Delta$is the aspect ratio of the metric space. Prior to our work, the best competitive ratio known for this problem was$O(k\ \text{poly}\log(n))$given by Azar et al. (STOC 2017). Our algorithm is based on a new covering linear program relaxation for$k$-server on HSTs. This LP naturally corresponds to the min-cost flow formulation of$k$-server, and easily extends to the case of time-windows. We give an online algorithm for obtaining a feasible fractional solution for this LP, and a primal dual analysis framework for accounting the cost of the solution. Together, they yield a new$k$-server algorithm with poly-logarithmic competitive ratio, and extend to the time-windows case as well. Our principal technical contribution lies in thinking of the covering LP as yielding a truncated covering LP at each internal node of the tree, which allows us to keep account of server movements across subtrees. We hope that this LP relaxation and the algorithm/analysis will be a useful tool for addressing$k$-server and related problems.

We give an$n^{2+o(1)}$-time algorithm for finding$s-t$min-cuts for all pairs of vertices$s$and$t$in a simple, undirected graph on$n$vertices. We do so by constructing a Gomory-Hu tree (or cut equivalent tree) in the same running time, thereby improving on the recent bound of$\tilde{O}(n^{2.5})$by Abboud et al. (STOC 2021). Our running time is nearly optimal as a function of$n$.

We give an algorithm to find a minimum cut in an edge-weighted directed graph with$n$vertices and$m$edges in$\tilde{O}(n\cdot\max\{m^{2/3},\ n\})$time. This improves on the 30 year old bound of$\tilde{O}(nm)$obtained by Hao and Orlin for this problem. Using similar techniques, we also obtain$\tilde{O}(n^{2}/\epsilon^{2})$-time$(1+{\epsilon})$-approximation algorithms for both the minimum edge and minimum vertex cuts in directed graphs, for any fixed$\epsilon$. Before our work, no (1 +$\epsilon)$-approximation algorithm better than the exact runtime of$\tilde{O}(nm)$is known for either problem. Our algorithms follow a two-step template. In the first step, we employ a partial sparsification of the input graph to preserve a critical subset of cut values approximately. In the second step, we design algorithms to find the (edge/vertex) mincut among the preserved cuts from the first step. For edge mincut, we give a new reduction to$\tilde{O}(\min\{{n}/m^{1/3}, \sqrt{n}\}){-}$calls of any maxflow subroutine, via packing arborescences in the sparsifier. For vertex mincut, we develop new local flow algorithms to identify small unbalanced cuts in the sparsified graph.

In this paper, we consider the problem of designing cut sparsifiers and sketches for directed graphs. To bypass known lower bounds, we allow the sparsifier/sketch to depend on the balance of the input graph, which smoothly interpolates between undirected and directed graphs. We give nearly matching upper and lower bounds for both for-all (cf. Benczúr and Karger, STOC 1996) and for-each (Andoni et al., ITCS 2016) cut sparsifiers/sketches as a function of cut balance, defined the maximum ratio of the cut value in the two directions of a directed graph (Ene et al., STOC 2016). We also show an interesting application of digraph sparsification via cut balance by using it to give a very short proof of a celebrated maximum flow result of Karger and Levine (STOC 2002).

This paper presents universal algorithms for clustering problems, including the widely studied k-median, k-means, and k-center objectives. The input is a metric space containing all potential client locations. The algorithm must select k cluster centers such that they are a good solution for any subset of clients that actually realize. Specifically, we aim for low regret, defined as the maximum over all subsets of the difference between the cost of the algorithm’s solution and that of an optimal solution. A universal algorithm’s solution sol for a clustering problem is said to be an (α, β)-approximation if for all subsets of clients C', it satisfies sol(C') ≤ α ⋅ opt(C') + β ⋅ mr, where opt(C') is the cost of the optimal solution for clients C' and mr is the minimum regret achievable by any solution. Our main results are universal algorithms for the standard clustering objectives of k-median, k-means, and k-center that achieve (O(1), O(1))-approximations. These results are obtained via a novel framework for universal algorithms using linear programming (LP) relaxations. These results generalize to other 𝓁_p-objectives and the setting where some subset of the clients are fixed. We also give hardness results showing that (α, β)-approximation is NP-hard if α or β is at most a certain constant, even for the widely studied special case of Euclidean metric spaces. This shows that in some sense, (O(1), O(1))-approximation is the strongest type of guarantee obtainable for universal clustering.

The emerging field of learning-augmented online algorithms uses ML techniques to predict future input parameters and thereby improve the performance of online algorithms. Since these parameters are, in general, real-valued functions, a natural approach is to use regression techniques to make these predictions. We introduce this approach in this paper, and explore it in the context of a general online search framework that captures classic problems like (generalized) ski rental, bin packing, minimum makespan scheduling, etc. We show nearly tight bounds on the sample complexity of this regression problem, and extend our results to the agnostic setting. From a technical standpoint, we show that the key is to incorporate online optimization benchmarks in the design of the loss function for the regression problem, thereby diverging from the use of off-the-shelf regression tools with standard bounds on statistical error.

We study combinatorial auctions in online environments with the goal of maximizing social welfare. In this problem, new items become available on each day and must be sold before their respective expiration dates. We design online auctions for the widely studied classes of submodular and XOS valuations, and show the following results: – For submodular valuations, we give an O(log m)-competitive mechanism for adversarial valuations and an O(1)-competitive mechanism for Bayesian valuations, where m is the total number of items. Both these mechanisms are computationally efficient and universally truthful for myopic agents, i.e., agents with no knowledge of the future. – For XOS valuations, we show that there is no online mechanism that can achieve a competitive ratio of o ((m/ log m)1/3) even in a Bayesian setting. Our lower bound holds even if we do not require truthfulness and/or computational efficiency of the mechanism. This establishes a sharp separation between XOS valuations and its subclass of submodular valuations for online combinatorial auctions. In contrast, no such separation exists for offline auctions, where the best bounds for both submodular and XOS valuations are O((log log m)3) for adversarial settings (Assadi and Singla, FOCS 2019) and O(1) for Bayesian settings (Dütting et al., FOCS 2017). In contrast to the above, if items do not expire and only need to be sold before the market closes, then we give a reduction from offline to online mechanisms that preserves the competitive ratio for all subadditive valuations (that includes XOS and submodular valuations), thereby achieving the same bounds as the respective best offline mechanisms.

The vertex connectivity of an m-edge n-vertex undirected graph is the smallest number of vertices whose removal disconnects the graph, or leaves only a singleton vertex. In this paper, we give a reduction from the vertex connectivity problem to a set of maxflow instances. Using this reduction, we can solve vertex connectivity in (mα) time for any α ≥ 1, if there is a mα-time maxflow algorithm. Using the current best maxflow algorithm that runs in m4/3+o(1) time (Kathuria, Liu and Sidford, FOCS 2020), this yields a m4/3+o(1)-time vertex connectivity algorithm. This is the first improvement in the running time of the vertex connectivity problem in over 20 years, the previous best being an Õ(mn)-time algorithm due to Henzinger, Rao, and Gabow (FOCS 1996). Indeed, no algorithm with an o(mn) running time was known before our work, even if we assume an (m)-time maxflow algorithm.

The Gomory-Hu tree or cut tree (Gomory and Hu, 1961) is a classic data structure for reporting s−t mincuts (and by duality, the values of s−t maxflows) for all pairs of vertices s and t in an undirected graph. Gomory and Hu showed that it can be computed using n−1 exact maxflow computations. Surprisingly, this remains the best algorithm for Gomory-Hu trees more than 50 years later, even for approximate mincuts. In this paper, we break this longstanding barrier and give an algorithm for computing a (1+є)-approximate Gomory-Hu tree using log(n) maxflow computations. Specifically, we obtain the runtime bounds we describe below.

This issue of SICOMP contains 14 specially selected papers from the 48th Annual ACM Symposium on Theory of Computing (STOC 2016), held June 18--June 21, 2016, in Cambridge, Massachusetts. The papers here were chosen to represent both the excellence and the broad range of the STOC program. The papers have been revised and extended by the authors and subjected to the standard thorough reviewing process of SICOMP. The program committee members were Alexandr Andoni, Sanjeev Arora, Allison Bishop, Avrim Blum, Keren Censor-Hillel, Timothy Chan, Chandra Chekuri, Jing Chen, Zeev Dvir, Fabrizio Grandoni, Parikshit Gopalan, Kasper Green Larsen, Huijia (Rachel) Lin, Konstantin Makarychev, Yishay Mansour (chair), Jakob Nordström, Debmalya Panigrahi, Prasad Raghavendra, Sofya Raskhodnikova, R Ravi, Mario Szegedy, Êva Tardos, Salil Vadhan, Avi Wigderson, and Ronald de Wolf. We briefly describe here the papers that appear in this special issue. In “Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders,” Shahar Dobzinski provides the first truthful mechanism for welfare maximization in combinatorial auctions with submodular bidders whose approximation ratio is $O(\sqrt{\log m})$. Previously the best ratio was $O(\log m)$. In “A Tight Space Bound for Consensus,” Leqi Zhu proves that every randomized wait-free (or obstruction-free) consensus protocol for $n$ processes must use at least $n-1$ registers. Previously, this bound was known only in the anonymous setting, while for the general case only a $\sqrt{n}$ bound was known. In “Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs,” Gil Cohen constructs a $2^{(\log\log n)^c}$-Ramsey graph for some universal constant $c$, a significant improvement in this direction. In the language of theoretical computer science, this resolves the problem of explicitly constructing dispersers for two $n$-bit sources with entropy ${polylog}(n)$. Previously, such dispersers could only support entropy $\Omega(n)$. In “Algorithmic Bayesian Persuasion,” Shaddin Dughmi and Haifeng Xu examines Bayesian persuasion through a computational lens for the first time. When the payoff distributions are i.i.d. across actions, the authors provide a polynomial-time optimal solution and a “simple” $(1-1/e)$-approximation. For independent but nonidentical distributions, \#P-hardness is proved. For the general case with a black-box sampling oracle, an FPTAS is provided and shown to be the best possible under the black-box model. In “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths,” Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai present a deterministic $(1 + o(1))$-approximation algorithm for solving the single-source shortest paths problem on distributed weighted networks in $O(n^{1/2+o(1)} + D^{1+o(1)})$ rounds, where $n$ is the number of nodes and $D$ is the diameter of the network. This improves upon previous results in being deterministic and completing in less time or in obtaining a smaller approximation factor. Moreover, it is almost tight due to a known lower bound. In “Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines,” Nikhil Bansal, Aravind Srinivasan, and Ola Svensson improve, by a small but fixed constant, the long-standing approximation factor of $3/2$ for the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. In “A Duality-Based Unified Approach to Bayesian Mechanism Design,” Yang Cai, Nikhil Devanur, and Seth Matthew Weinberg provide a duality-based unified framework for designing simple and approximately optimal auctions. Using this framework, the authors prove that either a posted-price mechanism or the Vickrey--Clarke--Groves auction with per-bidder entry fees achieves a constant-factor of the optimal revenue achievable by a Bayesian Incentive Compatible mechanism whenever buyers are unit-demand or additive, unifying previous breakthroughs of Chawla et al. and Yao, and improving both approximation ratios. In “A $(1+\varepsilon)$-Approximation for Makespan Scheduling with Precedence Constraints using LP Hierarchies,” Elaine Levey and Thomas Rothvoss consider the problem of scheduling $n$ unit size jobs with a precedence order on $m$ identical machines as to minimize the makespan. They prove that for any fixed $\epsilon$ and $m$, an LP-hierarchy lift of the time-indexed LP with a slightly super poly-logarithmic number of $r = (\log n)^{\Theta(\log \log n)}$ rounds provides a $(1 + \epsilon)$-approximation. The previous best approximation algorithms for this problem guarantee a $(2 - 7/(3m+1))$-approximation in polynomial time for $m \ge 4$ and $4/3$ for $m=3$. In “Bipartite Perfect Matching Is in Quasi-${{NC}}$,” Stephen Fenner, Rohit Gurjar, and Thomas Thierauf show that the bipartite perfect matching problem is in quasi-${{NC}}^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$, and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth. In “Exponential Separation of Communication and External Information,” Anat Ganor, Gillat Kol, and Ran Raz prove the first gap, an exponential gap, between external information complexity and communication complexity of a communication task. Previously such a separation was known only for the internal information vs communication complexity. This result has implication to the question of compressing communication protocols to the amount of information they reveal about the inputs. In “Constant-Round Interactive Proofs for Delegating Computation,” Omer Reingold, Guy Rothblum, and Ron Rothblum design efficient, constant-round interactive proofs. They show that for any statement that can be evaluated in polynomial time and space $S$, there exists a constant-round interactive protocol where the prover has polynomial runtime and the verifier has a runtime of about $n+\poly(S)$. Prior to this work, very little was known about the power of constant-round protocol. This result is a major step for the grand challenge of verifiable delegation of computation. In “Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem,” Sepehr Assadi, Sanjeev Khanna, and Yang Li resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For finding an $\alpha$-approximate set cover (for any $\alpha= o(\sqrt{n})$) using a single-pass streaming algorithm, they show that $\Theta(mn/\alpha)$ space is both sufficient and necessary (up to an $O(\log n)$ factor), where $m$ denotes number of the sets and $n$ denotes size of the universe. They further study the problem of estimating the size of a minimum set cover (as opposed to finding the actual sets) and achieve an additional saving of a factor of $\alpha$ in the space complexity, which is also the best possible. In “A Polynomial Lower Bound for Testing Monotonicity,” Aleksandrs Belovs and Eric Blais show a polynomial lower bound on query complexity for adaptive testers of monotonicity of an $n$-variate Boolean function. Prior to this work, similar lower bounds were known only for the nonadaptive testers, and proving similar bounds for adaptive testers has been a major challenge. In “Algorithmic Stability for Adaptive Data Analysis,” Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman take a solid step forward in the area of adaptive data analysis by establishing a clean, tight connection between the notion of differential privacy (max-KL stability) and design of adaptive queries. This connection improves a number of bounds that were known prior to this paper, and generalizes to handle more “data analysis" settings. We thank the authors, the program committee members, and the reviewers for STOC 2016 for their hard work, and we especially thank the SICOMP reviewers for their work in evaluating submitted papers.

We give a deterministic (global) min-cut algorithm for weighted undirected graphs that runs in time O(m1+ε) plus polylog ( n) max-flow computations. Using the current best max-flow algorithms, this results in an overall running time of ~O(m·min(√m, n2/3)) for weighted graphs, and m4/3+o(1)for unweighted (multi)-graphs. This is the first improvement in the running time of deterministic algorithms for the min-cut problem on general (weighted/multi) graphs since the early 1990s when a running time bound of ~O(mn) was established for this problem.

In this paper, we consider the problem of assigning 2-dimensional vector jobs to identical machines online so to minimize the maximum load on any dimension of any machine. For arbitrary number of dimensions d, this problem is known as vector scheduling, and recent research has established the optimal competitive ratio as O((log d)/(log log d)) (Im et al. FOCS 2015, Azar et al. SODA 2018). But, these results do not shed light on the situation for small number of dimensions, particularly for d = 2 which is of practical interest. In this case, a trivial analysis shows that the classic list scheduling greedy algorithm has a competitive ratio of 3. We show the following improvements over this baseline in this paper: - We give an improved, and tight, analysis of the list scheduling algorithm establishing a competitive ratio of 8/3 for two dimensions. - If the value of opt is known, we improve the competitive ratio to 9/4 using a variant of the classic best fit algorithm for two dimensions. - For any fixed number of dimensions, we design an algorithm that is provably the best possible against a fractional optimum solution. This algorithm provides a proof of concept that we can simulate the optimal algorithm online up to the integrality gap of the natural LP relaxation of the problem.

Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defined as the maximum difference between the solution’s cost and that of an optimal solution in hindsight once the input has been realized. For graph problems in P, such as shortest path and minimum spanning tree, robust polynomial-time algorithms that obtain a constant approximation on regret are known. In this paper, we study robust algorithms for minimizing regret in NP-hard graph optimization problems, and give constant approximations on regret for the classical traveling salesman and Steiner tree problems.

In this paper, we initiate the study of the weighted paging problem with predictions. This continues the recent line of work in online algorithms with predictions, particularly that of Lykouris and Vassilvitski (ICML 2018) and Rohatgi (SODA 2020) on unweighted paging with predictions. We show that unlike unweighted paging, neither a fixed lookahead nor knowledge of the next request for every page is sufficient information for an algorithm to overcome existing lower bounds in weighted paging. However, a combination of the two, which we call the strong per request prediction (SPRP) model, suffices to give a 2-competitive algorithm. We also explore the question of gracefully degrading algorithms with increasing prediction error, and give both upper and lower bounds for a set of natural measures of prediction error.

A popular line of recent research incorporates ML advice in the design of online algorithms to improve their performance in typical instances. These papers treat the ML algorithm as a black-box, and redesign online algorithms to take advantage of ML predictions. In this paper, we ask the complementary question: can we redesign ML algorithms to provide better predictions for online algorithms? We explore this question in the context of the classic rent-or-buy problem, and show that incorporating optimization benchmarks in ML loss functions leads to significantly better performance, while maintaining a worst-case adversarial result when the advice is completely wrong. We support this finding both through theoretical bounds and numerical simulations.

We study the problem of learning opinions in social networks. The learner observes the states of some sample nodes from a social network, and tries to infer the states of other nodes, based on the structure of the network. We show that sample-efficient learning is impossible when the network exhibits strong noise, and give a polynomial-time algorithm for the problem with nearly optimal sample complexity when the network is sufficiently stable.

We consider the (weighted) Paging with Time Windows problem, which is identical to the classical weighted paging problem but where each page request only needs to be served by a given deadline. This problem arises in many practical applications of online caching, such as the deadline I/O scheduler in the Linux kernel and video-on-demand streaming. From a theoretical perspective, this generalizes the caching problem to allow delayed service, a line of work that has recently gained traction in online algorithms (e.g., Emek et al. STOC '16, Azar et al. STOC '17, Azar and Touitou FOCS '19, etc.).

We investigate the computational complexity of minimizing the source side-effect in order to remove a given number of tuples from the output of a conjunctive query. This is a variant of the well-studied deletion propagation problem, the difference being that we are interested in removing the smallest subset of input tuples to remove a given number of output tuples while deletion propagation focuses on removing a specific output tuple. We call this the Aggregated Deletion Propagation problem. We completely characterize the poly-time solvability of this problem for arbitrary conjunctive queries without self-joins. This includes a poly-time algorithm to decide solvability, as well as an exact structural characterization of NP-hard instances. We also provide a practical algorithm for this problem (a heuristic for NP-hard instances) and evaluate its experimental performance on real and synthetic datasets.

In recent years, a range of online applications have facilitated resource sharing among users, resulting in a significant increase in resource utilization. In all such applications, sharing one’s resources or skills with other agents increases social welfare. In general, each agent will look for other agents whose available resources complement hers, thereby forming natural sharing groups. In this paper, we study settings where a large population self-organizes into sharing groups. In many cases, centralized optimization approaches for creating an optimal partition of the user population are infeasible because either the central authority does not have the necessary information to compute an optimal partition, or it does not have the power to enforce a partition. Instead, the central authority puts in place an incentive structure in the form of a utility sharing method, before letting the participants form the sharing groups by themselves. We first analyze a simple equal-sharing method, which is the one most typically encountered in practice and show that it can lead to highly inefficient equilibria. We then propose a Shapley-sharing method and show that it significantly improves overall social welfare.

We initiate the algorithmic study of retracting a graph into a cycle in the graph, which seeks a mapping of the graph vertices to the cycle vertices, so as to minimize the maximum stretch of any edge, subject to the constraint that the restriction of the mapping to the cycle is the identity map. This problem has its roots in the rich theory of retraction of topological spaces, and has strong ties to well-studied metric embedding problems such as minimum bandwidth and 0-extension. Our first result is an O(min{k, sqrt{n}})-approximation for retracting any graph on n nodes to a cycle with k nodes. We also show a surprising connection to Sperner's Lemma that rules out the possibility of improving this result using natural convex relaxations of the problem. Nevertheless, if the problem is restricted to planar graphs, we show that we can overcome these integrality gaps using an exact combinatorial algorithm, which is the technical centerpiece of the paper. Building on our planar graph algorithm, we also obtain a constant-factor approximation algorithm for retraction of points in the Euclidean plane to a uniform cycle.

We study the use of predictions by multiple experts (such as machine learning algorithms) to improve the performance of online algorithms. In particular, we consider the classical rent-or-buy problem (also called ski rental), and obtain algorithms that provably improve their performance over the adversarial scenario by using these predictions. We also prove matching lower bounds to show that our algorithms are the best possible, and perform experiments to empirically validate their performance in practice

We design multi-unit auctions for budget-constrained bidders in the Bayesian setting. Our auctions are supply-monotone, which allows the auction to be run online without knowing the number of items in advance, and achieve asymptotic revenue optimality. We also give an efficient algorithm for implementing our auction by using a succinct and efficiently implementable characterization of supply-monotonicity in the Bayesian setting.

On hypergraphs with m hyperedges and n vertices, where p denotes the total size of the hyperedges, we provide the following results: We give an algorithm that runs in Õ(mn2k–2) time for finding a minimum k-cut in hypergraphs of arbitrary rank. This algorithm betters the previous best running time for the minimum k-cut problem, for k > 2. We give an algorithm that runs in Õ(nmax{r, 2k–2}) time for finding a minimum k-cut in hypergraphs of constant rank r. This algorithm betters the previous best running times for both the minimum cut and minimum k-cut problems for dense hypergraphs. Both of our algorithms are Monte Carlo, i.e., they return a minimum k-cut (or minimum cut) with high probability. These algorithms are obtained as instantiations of a generic branching randomized contraction technique on hypergraphs, which extends the celebrated work of Karger and Stein on recursive contractions in graphs. Our techniques and results also extend to the problems of minimum hedge-cut and minimum hedge-k-cut on hedgegraphs, which generalize hypergraphs.

Motivated by applications in cloud computing, we study the classical online caching problem for a cache of variable size, where the algorithm pays a maintenance cost that monotonically increases with cache size. This captures not only the classical setting of a fixed cache size, which corresponds to a maintenance cost of 0 for a cache of size at most k and ∞ otherwise, but also other natural settings in the context of cloud computing such as a concave rental cost on cache size. We call this the elastic caching problem. Our results are: (a) a randomized algorithm with a competitive ratio of O(log n) for maintenance cost that is an arbitrary function of cache size, (b) a deterministic algorithm with a competitive ratio of 2 for concave, or more generally submodular maintenance costs, (c) a deterministic n-competitive algorithm when the cost function is any monotone non-negative set function, and (d) a randomized constant-factor approximation algorithm for the offline version of the problem. Our algorithms are based on a configuration LP formulation of the problem, for which our main technical contribution is to maintain online a feasible fractional solution that can be converted to an integer solution using existing rounding techniques.

We give new upper and lower bounds for the dynamic set cover problem. First, we give a (1+є) f-approximation for fully dynamic set cover in O(f2logn/є5) (amortized) update time, for any є > 0, where f is the maximum number of sets that an element belongs to. In the decremental setting, the update time can be improved to O(f2/є5), while still obtaining an (1+є) f-approximation. These are the first algorithms that obtain an approximation factor linear in f for dynamic set cover, thereby almost matching the best bounds known in the offline setting and improving upon the previous best approximation of O(f2) in the dynamic setting.

We present a general framework for constructing cut sparsifiers in undirected graphs---weighted subgraphs for which every cut has the same weight as the original graph, up to a multiplicative factor of $(1 \pm \epsilon)$. Using this framework, we simplify, unify, and improve upon previous sparsification results. As simple instantiations of this framework, we show that sparsifiers can be constructed by sampling edges according to their strength (a result of Benczúr and Karger [ Approximating s-t minimum cuts in o͂(n$^2$) time, in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, ACM, New York, 1996, pp. 47--55], [ SIAM J. Comput., 44 (2015), pp. 290--319]), effective resistance (a result of Spielman and Srivastava [ SIAM J. Comput., 40 (2011), pp. 1913--1926]), or edge connectivity. Sampling according to edge connectivity is the most aggressive method, and the most challenging to analyze. Our proof that this method produces sparsifiers resolves an open question of Benczúr and Karger. While the above results are interesting from a combinatorial standpoint, we also prove new algorithmic results. In particular, we give the first (optimal) $O(m)$-time sparsification algorithm for unweighted graphs. Our algorithm has a running time of $O(m) + \tilde{O}(n/\epsilon^2)$ for weighted graphs, which is also linear unless the input graph is very sparse itself. In both cases, this improves upon the previous best running times (due to Benczúr and Karger [ Approximating s-t minimum cuts in o͂(n$^2$) time, in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, ACM, New York, 1996, pp. 47--55], [ SIAM J. Comput., 44 (2015), pp. 290--319]) of $O(m\log^2 n)$ (for the unweighted case) and $O(m\log^3 n)$ (for the weighted case), respectively. Our algorithm constructs sparsifiers that contain $O(n\log n/\epsilon^2)$ edges in expectation. A key ingredient of our proofs is a natural generalization of Karger's bound on the number of small cuts in an undirected graph. Given the numerous applications of Karger's bound, we suspect that our generalization will also be of independent interest.

Modern data centers face a key challenge of effectively serving user requests that arrive online. Such requests are inherently multidimensional and characterized by demand vectors over multiple resources such as processor cycles, storage space, and network bandwidth. Typically, different resources require different objectives to be optimized, and $L_r$ norms of loads are among the most popular objectives considered. Furthermore, the server clusters are also often heterogeneous making the scheduling problem more challenging. To address these problems, we consider the online vector scheduling problem in this paper. Introduced by Chekuri and Khanna in 2006, vector scheduling is a generalization of classical load balancing, where every job has a vector load instead of a scalar load. The scalar problem, introduced by Graham in 1966, and its many variants (identical and unrelated machines, makespan and $L_r$ norm optimization, offline and online jobs, etc.) have been extensively studied over the last 50 years. In this paper, we resolve the online complexity of the vector scheduling problem and its important generalizations---for all $L_r$ norms and in both the identical and unrelated machines settings. For an instance with $m$ machines and $d$ dimensions, our main results are: For identical machines, we show that the optimal competitive ratio is $\Theta(\log d / \log \log d)$ by giving an online lower bound and an algorithm with an asymptotically matching competitive ratio. The lower bound is technically challenging, and is obtained via an online lower bound for the minimum monochromatic clique problem using a novel online coloring game and randomized coding scheme. Our techniques also extend to asymptotically tight upper and lower bounds for general $L_r$ norms. For unrelated machines, we show that the optimal competitive ratio is $\Theta(\log m + \log d)$ by giving an online lower bound that matches a previously known upper bound. Unlike identical machines, however, extending these results, particularly the upper bound, to general $L_r$ norms requires new ideas. In particular, we use a carefully constructed potential function that balances the individual $L_r$ objectives with the overall (convexified) min-max objective to guide the online algorithm and track the changes in potential to bound the competitive ratio.

We study randomized algorithms for the online vector bin packing and vector scheduling problems. For vector bin packing, we achieve a competitive ratio of Õ(d1/B), where d is the number of dimensions and B the size of a bin. This improves the previous bound of Õ(d1/(B-1)) by a polynomial factor, and is tight up to logarithmic factors. For vector scheduling, we show a lower bound of on the competitive ratio of randomized algorithms, which is the first result for randomized algorithms and is asymptotically tight. Finally, we analyze the widely used “power of two choices’ algorithm for vector scheduling, and show that its competitive ratio is , which is optimal up to the additive O(log log n) term that also appears in the scalar version of this algorithm.

In this paper, we consider the problem of assigning jobs online to machines with non-uniform speeds (also called related machines) so to optimize a given norm of the machine loads. A long line of work, starting with the seminal work of Graham in the 1960s, has led to tight competitive ratios for all ℓq norms for two scenarios: the special case of identical machines (uniform machine speeds) and the more general setting of unrelated machines (jobs have arbitrary processing times on machines). For non-uniform machine speeds, however, the only known result was a constant competitive competitive ratio for the makespan (ℓ∞) norm, via the so-called slowest-fit algorithm (Aspnes, Azar, Fiat, Plotkin, and Waarts, JACM ’97). Our first result in this paper is to obtain the first constant-competitive algorithm for scheduling on related machines for any arbitrary ℓq norm.

Motivated by the popularity of online ride and delivery services, we study natural variants of classical multi-vehicle minimum latency problems where the objective is to route a set of vehicles located at depots to serve requests located on a metric space so as to minimize the total latency. In this paper, we consider point-to-point requests that come with source-destination pairs and release-time constraints that restrict when each request can be served. The point-to-point requests and release-time constraints model taxi rides and deliveries. For all the variants considered, we show constant-factor approximation algorithms based on a linear programming framework. To the best of our knowledge, these are the first set of results for the aforementioned variants of the minimum latency problems. Furthermore, we provide an empirical study of heuristics based on our theoretical algorithms on a real data set of taxi rides.

We present the first online algorithms for the nonuniform, multicommodity buy-at-bulk (MC-BB) network design problem. Our competitive ratios qualitatively match the best known approximation factors for the corresponding offline problems. In particular, we show (a) a polynomial time online algorithm with a polylogarithmic competitive ratio for the MC-BB problem in undirected edge-weighted graphs, (b) a quasi-polynomial time online algorithm with a polylogarithmic competitive ratio for the MC-BB problem in undirected node-weighted graphs, (c) for any fixed $\epsilon > 0$, a polynomial time online algorithm with a competitive ratio of $\tilde{O}\big(k^{\frac{1}{2}+\epsilon})$ (where $k$ is the number of demands, and the tilde hides polylog factors) for MC-BB in directed graphs, and (d) algorithms with matching competitive ratios for the prize-collecting variant of all the preceding problems. Prior to our work, a logarithmic competitive ratio was known for undirected, edge-weighted graphs only for the special case of uniform costs [B. Awerbuch and Y. Azar, FOCS, 1997, pp. 542--547], and a polylogarithmic-competitive algorithm was known for the edge-weighted single-sink problem [A. Meyerson, Procedings of SPAA, 2004, pp. 275--280]. We believe no online algorithm was known in the node-weighted and directed settings, even for uniform costs. Our main technical contribution is an online reduction theorem of MC-BB problems to their single-sink counterparts. We use the concept of junction-tree solutions from [C. Chekuri, M. T. Hajiaghayi, G. Kortsarz, and M. R. Salavatipour, Proceedings of FOCS, 2006, pp. 677--686], which play an important role in solving the offline versions of the problem via a greedy subroutine---an inherently offline procedure. We use just the existence of good junction-trees for our reduction.

In various matching market settings, such as hospital-doctor matching markets (Hatfield and Milgrom 2005), the existence of stable outcomes depends on substitutability of preferences. But can these stable matchings be computed efficiently, as in the one-to-one matching case? The algorithm of (Hatfield and Milgrom 2005) requires efficient implementation of a choice function over substitutable preferences. We show that even given efficient access to a value oracle or preference relation satisfying substitutability, exponentially many queries may be required in the worst case to implement a choice function. Indeed, this extends to examples where a stable matching requires exponential time to compute. We characterize the computational complexity of stable matchings by showing that efficient computation of a choice function is equivalent to efficient verification—determining whether or not, for a given set, the most preferred subset is the entire set itself. Clearly, verification is necessary for computation, but we show that it is also sufficient: specifically, given a verifier, we design a polynomial-time algorithm for computing a choice function, implying an efficient algorithm for stable matching. We then show that a verifier can be implemented efficiently for various classes of functions, such as submodular functions, implying efficient stable matching algorithms for a broad range of settings. We also investigate the effect of ties in the preference order, which causes complications both in defining substitutes and in computation. In this case, we tightly connect the computational complexity of the choice function to a measure on the number of ties.

Motivated by denial-of-service network attacks, we introduce the symmetric interdiction model, where both the interdictor and the optimizer are subject to the same constraints of the underlying optimization problem. We give a general framework that relates optimization to symmetric interdiction for a broad class of optimization problems. We then study the symmetric matching interdiction problem - with applications in traffic engineering - in more detail. This problem can be simply stated as follows: find a matching whose removal minimizes the size of the maximum matching in the remaining graph. We show that this problem is APX-hard, and obtain a 3/2-approximation algorithm that improves on the approximation guarantee provided by the general framework.

The rapid growth of the Internet has led to the widespread use of newer and richer models of online shopping and delivery services. The race to efficient large scale on-demand delivery has transformed such services into complex networks of shoppers (typically working in the stores), stores, and consumers. The efficiency of processing orders in stores is critical to the profitability of the business model. Motivated by this setting, we consider the following problem: given a set of shopping orders each consisting of a few items, how to best partition the orders among a given number of shoppers working for an online shopping service? Formulating this as an optimization problem, we propose a family of simple and efficient algorithms that admit natural constraints such as number of items a shopper can process in this setting. In addition to showing provable guarantees for the algorithms, we also demonstrate their efficiency in practice on real-world data, outperforming strong baselines.

Let R, B be a set of n points in R^d, for constant d, where the points of R have integer supplies, points of B have integer demands, and the sum of supply is equal to the sum of demand. Let d(.,.) be a suitable distance function such as the L_p distance. The transportation problem asks to find a map tau : R x B --> N such that sum_{b in B}tau(r,b) = supply(r), sum_{r in R}tau(r,b) = demand(b), and sum_{r in R, b in B} tau(r,b) d(r,b) is minimized. We present three new results for the transportation problem when d(.,.) is any L_p metric: * For any constant epsilon > 0, an O(n^{1+epsilon}) expected time randomized algorithm that returns a transportation map with expected cost O(log^2(1/epsilon)) times the optimal cost. * For any epsilon > 0, a (1+epsilon)-approximation in O(n^{3/2}epsilon^{-d}polylog(U)polylog(n)) time, where U is the maximum supply or demand of any point. * An exact strongly polynomial O(n^2 polylog n) time algorithm, for d = 2.

We study utility games (Vetta, FOCS 2002) where a set of players join teams to produce social utility, and receive individual utility in the form of payments in return. These games have many natural applications in competitive settings such as labor markets, crowdsourcing, etc. The efficiency of such a game depends on the profit sharing mechanism - the rule that maps utility produced by the players to their individual payments. We study three natural and widely used profit sharing mechanisms - egalitarian or equal sharing, marginal gain or value addition when a player joins, and marginal loss or value depletion when a player leaves. For these settings, we give tight bounds on the price of anarchy, thereby allowing comparison between these popular mechanisms from a (worst case) social welfare perspective.

We initiate the study of hedge connectivity of undirected graphs, motivated by dependent edge failures in real-world networks. In this model, edges are partitioned into groups called hedges that fail together. The hedge connectivity of a graph is the minimum number of hedges whose removal disconnects the graph. We give a polynomial-time approximation scheme and a quasi-polynomial exact algorithm for hedge connectivity. This provides strong evidence that the hedge connectivity problem is tractable, which contrasts with prior work that established the intractability of the corresponding s-t min-cut problem. Our techniques also yield new combinatorial and algorithmic results in hypergraph connectivity. Next, we study the behavior of hedge graphs under uniform random sampling of hedges. We show that unlike graphs, all cuts in the sample do not converge to their expected value in hedge graphs. Nevertheless, the min-cut of the sample does indeed concentrate around the expected value of the original min-cut. This leads to a sharp threshold on hedge survival probabilities for graph disconnection. To the best of our knowledge, this is the first network reliability analysis under dependent edge failures.

In this article, we introduce the online service with delay problem. In this problem, there are n points in a metric space that issue service requests over time, and there is a server that serves these requests. The goal is to minimize the sum of distance traveled by the server and the total delay (or a penalty function thereof) in serving the requests. This problem models the fundamental tradeoff between batching requests to improve locality and reducing delay to improve response time, which has many applications in operations management, operating systems, logistics, supply chain management, and scheduling. Our main result is to show a poly-logarithmic competitive ratio for the online service with delay problem. This result is obtained by an algorithm that we call the preemptive service algorithm . The salient feature of this algorithm is a process called preemptive service, which uses a novel combination of (recursive) time forwarding and spatial exploration on a metric space. We also generalize our results to k > 1 servers and obtain stronger results for special metrics such as uniform and star metrics that correspond to (weighted) paging problems.

In this paper, we give new results for the set cover problem in the fully dynamic model. In this model, the set of "active" elements to be covered changes over time. The goal is to maintain a near-optimal solution for the currently active elements, while making few changes in each timestep. This model is popular in both dynamic and online algorithms: in the former, the goal is to minimize the update time of the solution, while in the latter, the recourse (number of changes) is bounded. We present generic techniques for the dynamic set cover problem inspired by the classic greedy and primal-dual offline algorithms for set cover. The former leads to a competitive ratio of O(lognt), where nt is the number of currently active elements at timestep t, while the latter yields competitive ratios dependent on ft, the maximum number of sets that a currently active element belongs to. We demonstrate that these techniques are useful for obtaining tight results in both settings: update time bounds and limited recourse, exhibiting algorithmic techniques common to these two parallel threads of research.

We give the first polynomial-time online algorithm for the node-weighted Steiner forest problem with a poly-logarithmic competitive ratio. The competitive ratio of our algorithm is optimal up to a logarithmic factor. For the special case of graphs with an excluded fixed minor (e.g., planar graphs), we obtain a logarithmic competitive ratio, which is optimal up to a constant, using a different online algorithm. Both these results are obtained as special cases of generic results for a large class of problems that can be encoded as online $\{0, 1\}$- proper functions. Our results are obtained by using a new framework for online network design problems that we call disk paintings. The central idea in this technique is to amortize the cost of primal updates to a set of carefully selected mutually disjoint fixed-radius dual disks centered at a subset of terminals. We hope that this framework will be useful for other online network design problems.

No abstract available.

We present online algorithms for covering and packing problems with (non-linear) convex objectives. The convex covering problem is defined as: minxϵR+nf(x) s.t. Ax ≥ 1, where f:R+n→ R+is a monotone convex function, and A is an m×n matrix with non-negative entries. In the online version, a new row of the constraint matrix, representing a new covering constraint, is revealed in each step and the algorithm is required to maintain a feasible and monotonically non-decreasing assignment x over time. We also consider a convex packing problem defined as: maxyϵR+mΣj=1myj - g(ATy), where g:R+n→R+is a monotone convex function. In the online version, each variable yj arrives online and the algorithm must decide the value of yj on its arrival. This represents the Fenchel dual of the convex covering program, when g is the convex conjugate of f. We use a primal-dual approach to give online algorithms for these generic problems, and use them to simplify, unify, and improve upon previous results for several applications.

We study the online budgeted allocation (also called Adwords) problem, where a set of impressions arriving online are allocated to a set of budget-constrained advertisers to maximize revenue. Motivated by connections to Internet advertising, several variants of this problem have been studied since the seminal work of Mehta, Saberi, Vazirani, and Vazirani (FOCS 2005). However, this entire body of work focuses on a single budget for every advertising campaign, whereas in order to fully represent the actual agenda of an advertiser, an advertising budget should be expressible over multiple tiers of user-attribute granularity. A simple example is an advertising campaign that is constrained by an overall budget but is also accompanied by a set of sub-budgets for each target demographic. In such a contract scheme, an advertiser can specify their true user-targeting goals, allowing the publisher to fulfill them through relevant allocations.

We present the first non-trivial online algorithms for the non-uniform, multicommodity buy-at-bulk (MC-BB) network design problem. Our competitive ratios qualitatively match the best known approximation factors for the corresponding offline problems. In particular, we show:1. A polynomial time online algorithm with a poly-logarithmic competitive ratio for the MC-BB problem in undirected edge-weighted graphs.2. A quasi-polynomial time online algorithm with a poly-logarithmic competitive ratio for the MC-BB problem in undirected node-weighted graphs.3. For any fixed ε > 0, a polynomial time online algorithm with a competitive ratio of O̅(k{1/2+ε}polylog(n)) (where k is the number of demands) for MC-BB in directed graphs.4. Algorithms with matching competitive ratios for the prize-collecting variants of all the above problems. Prior to our work, a logarithmic competitive ratio was known for undirected, edge-weighted graphs only for the special case of uniform costs (Awerbuch and Azar, FOCS 1997), and a polylogarithmic competitive ratio was known for the edge-weighted single-sink problem (Meyerson, SPAA 2004). To the best of our knowledge, no previous online algorithm was known, even for uniform costs, in the node-weighted and directed settings. Our main engine for the results above is an online reduction theorem of MC-BB problems to their single-sink (SS-BB) counterparts. We use the concept of junction-tree solutions (Chekuri et al., FOCS 2006) that play an important role in solving the offline versions of the problem via a greedy subroutine -- an inherently offline procedure. Our main technical contribution is in designing an online algorithm using only the existence of good junction-trees to reduce an MC-BB instance to multiple SS-BB sub-instances. Along the way, we also give the first non-trivial online node-weighted/directed single-sink buy-at-bulk algorithms. In addition to the new results, our generic reduction also yields new proofs of recent results for the online node-weighted Steiner forest and online group Steiner forest problems.

Modern data centers face a key challenge of effectively serving user requests that arrive online. Such requests are inherently multi-dimensional and characterized by demand vectors over multiple resources such as processor cycles, storage space, and network bandwidth. Typically, different resources require different objectives to be optimized, and Lrnorms of loads are among the most popular objectives considered. Furthermore, the server clusters are also often heterogeneous making the scheduling problem more challenging. To address these problems, we consider the online vector scheduling problem in this paper. Introduced by Chekuri and Khanna (SIAM J. of Comp. 2006), vector scheduling is a generalization of classical load balancing, where every job has a vector load instead of a scalar load. The scalar problem, introduced by Graham in 1966, and its many variants (identical and unrelated machines, makespan and Lr-norm optimization, offline and online jobs, etc.) have been extensively studied over the last 50 years. In this paper, we resolve the online complexity of the vector scheduling problem and its important generalizations - for all Lrnorms and in both the identical and unrelated machines settings. Our main results are: · For identical machines, we show that the optimal competitive ratio is Θ(log d/ log log d) by giving an online lower bound and an algorithm with an asymptotically matching competitive ratio. The lower bound is technically challenging, and is obtained via an online lower bound for the minimum mono-chromatic clique problem using a novel online coloring game and randomized coding scheme. Our techniques also extend to asymptotically tight upper and lower bounds for general Lrnorms. · For unrelated machines, we show that the optimal competitive ratio is Θ(log m + log d) by giving an online lower bound that matches a previously known upper bound. Unlike identical machines, however, extending these results, particularly the upper bound, to general Lrnorms requires new ideas. In particular, we use a carefully constructed potential function that balances the individual Lrobjectives with the overall (convexified) min-max objective to guide the online algorithm and track the changes in potential to bound the competitive ratio.

In recent years, there has been a growing interest in speed scaling algorithms, where a set of jobs need to be scheduled on a machine with variable speed so as to optimize the flow-times of the jobs and the energy consumed by the machine. A series of results have culminated in constant-competitive algorithms for this problem in the clairvoyant model, i.e., when job parameters are revealed on releasing a job (Bansal, Pruhs, and Stein, SODA 2007; Bansal, Chan, and Pruhs, SODA 2009). Our main contribution in this paper is the first constant-competitive speed scaling algorithm in the non-clairvoyant model, which is typically used in the scheduling literature to model practical settings where job volume is revealed only after the job has been completely processed. Unlike in the clairvoyant model, the speed scaling problem in the non-clairvoyant model is non-trivial even for a single job. Our non-clairvoyant algorithm is defined by using the existing clairvoyant algorithm in a novel inductive way, which then leads to an inductive analytical tool that may be of independent interest for other online optimization problems. We also give additional algorithmic results and lower bounds for speed scaling on multiple identical parallel machines.

We consider a generic online allocation problem that generalizes the classical online set cover framework by considering requests comprising a set of elements rather than a single element. This problem has multiple applications in cloud computing, crowd sourcing, facility planning, etc. Formally, it is an online covering problem where each online step comprises an offline covering problem. In addition, the covering sets are capacitated, leading to packing constraints. We give a randomized algorithm for this problem that has a nearly tight competitive ratio in both objectives: overall cost and maximum capacity violation. Our main technical tool is an online algorithm for packing/covering LPs with nested constraints, which may be of interest in other applications as well.

A key characteristic of a successful online market is the large participation of agents (producers and consumers) on both sides of the market. While there has been a long line of impressive work on understanding such markets in terms of revenue maximizing (also called max-sum) objectives, particularly in the context of allocating online impressions to interested advertisers, fairness considerations have surprisingly not received much attention in online allocation algorithms. Allocations that are inherently fair to participating entities, we believe, will contribute significantly to retaining current participants and attracting new ones in the long run, thereby enhancing the performance of online markets. We give two generic online allocation algorithms to address this problem. In the first algorithm, we address the max-min fairness objective which is defined as the minimum ratio among all advertisers of the actual revenue obtained by the allocation to given target revenues. The second algorithm considers a hybrid objective of max-sum with a revenue penalty for each advertiser who misses her revenue target. We consider a penalty that is linear in the difference between the target and the actual revenue. For both these objectives, we give online algorithms that achieve a competitive ratio of $(1-\epsilon)$ for any $\epsilon > 0$ assuming an IID input.

We give the first polynomial-time online algorithm for the node-weighted Steiner forest problem with a poly-logarithmic competitive ratio. The competitive ratio of our algorithm is optimal up to a logarithmic factor. For the special case of graphs with an excluded fixed minor (e.g., planar graphs), we obtain a logarithmic competitive ratio, which is optimal up to a constant, using a different online algorithm. Both these results are obtained as special cases of generic results for a large class of problems that can be encoded as online 0, 1-proper functions. Our results are obtained by using a new framework for online network design problems that we call disk paintings. The central idea in this technique is to amortize the cost of primal updates to a set of carefully selected mutually disjoint fixed-radius dual disks centered at a subset of terminals. We hope that this framework will be useful for other online network design problems.

Recent work has shown that the classical framework of solving optimization problems by obtaining a fractional solution to a linear program (LP) and rounding it to an integer solution can be extended to the online setting using primal-dual techniques. The success of this new framework for online optimization can be gauged from the fact that it has led to progress in several longstanding open questions. However, to the best of our knowledge, this framework has previously been applied to LPs containing only packing or only covering constraints, or minor variants of these. We extend this framework in a fundamental way by demonstrating that it can be used to solve mixed packing and covering LPs online, where packing constraints are given offline and covering constraints are received online. The objective is to minimize the maximum multiplicative factor by which any packing constraint is violated, while satisfying the covering constraints. Our results represent the first algorithm that obtains a polylogarithmic competitive ratio for solving mixed LPs online. We then consider two canonical examples of mixed LPs: unrelated machine scheduling with startup costs, and capacity constrained facility location. We use ideas generated from our result for mixed packing and covering to obtain polylogarithmic-competitive algorithms for these problems. We also give lower bounds to show that the competitive ratios of our algorithms are nearly tight.

A search engine aims to return a set of relevant documents in response to a query, while minimizing the response time. This has led to the use of a tiered index, where the search engine maintains a small cache of documents that can serve a large fraction of queries. We give a novel algorithm for the selection of documents in a tiered index for commerce search (i.e. users searching for products on the web) that effectively exploits the superior structural characteristics of commerce search queries. This is in sharp contrast to previous approaches to tiered indexing that were aimed at general web search where queries are typically unstructured. We theoretically analyze our algorithms and give performance guarantees even in worst-case scenarios. We then complement and strengthen our theoretical claims by performing exhaustive experiments on real-world commerce search data, and show that our algorithm outperforms state-of-the-art tiered indexing techniques that were developed for general web search.

The online matching problem has received significant attention in recent years because of its connections to allocation problems in Internet advertising, crowd-sourcing, etc. In these real-world applications, the typical goal is not to maximize the number of allocations, rather it is to maximize the number of successful allocations, where success of an allocation is governed by a stochastic process which follows the allocation. To address such applications, we propose and study the online matching problem with stochastic rewards (called the ONLINE STOCHASTIC MATCHING problem) in this paper. Our problem also has close connections to the existing literature on stochastic packing problems, in fact, our work initiates the study of online stochastic packing problems. We give a deterministic algorithm for the ONLINE STOCHASTIC MATCHING problem whose competitive ratio converges to (approximately) 0.567 for uniform and vanishing probabilities. We also give a randomized algorithm which outperforms the deterministic algorithm for higher probabilities. Finally, we complement our algorithms by giving an upper bound on the competitive ratio of any algorithm for this problem. This result shows that the best achievable competitive ratio for the ONLINE STOCHASTIC MATCHING problem is provably worse than that for the (non-stochastic) online matching problem.

The phenomenal growth in the volume of easily accessible information via various web-based services has made it essential for service providers to provide users with personalized representative summaries of such information. Further, online commercial services including social networking and micro-blogging websites, e-commerce portals, leisure and entertainment websites, etc. recommend interesting content to users that is simultaneously diverse on many different axes such as topic, geographic specificity, etc. The key algorithmic question in all these applications is the generation of a succinct, representative, and relevant summary from a large stream of data coming from a variety of sources. In this paper, we formally model this optimization problem, identify its key structural characteristics, and use these observations to design an extremely scalable and efficient algorithm. We analyze the algorithm using theoretical techniques to show that it always produces a nearly optimal solution. In addition, we perform large-scale experiments on both real-world and synthetically generated datasets, which confirm that our algorithm performs even better than its analytical guarantees in practice, and also outperforms other candidate algorithms for the problem by a wide margin.

We obtain the first online algorithms for the node-weighted Steiner tree, Steiner forest and group Steiner tree problems that achieve a poly-logarithmic competitive ratio. Our algorithm for the Steiner tree problem runs in polynomial time, while those for the other two problems take quasi-polynomial time. Our algorithms can be viewed as online LP rounding algorithms in the framework of Buchbinder and Naor (Foundations and Trends in Theoretical Computer Science, 2009); however, while the natural LP formulation of these problems do lead to fractional algorithms with a poly-logarithmic competitive ratio, we are unable to round these LPs online without losing a polynomial factor. Therefore, we design new LP formulations for these problems drawing on a combination of paradigms such as spider decompositions, low-depth Steiner trees, generalized group Steiner problems, etc. and use the additional structure provided by these to round the more sophisticated LPs losing only a poly-logarithmic factor in the competitive ratio. As further applications of our techniques, we also design polynomial-time online algorithms with poly-logarithmic competitive ratios for two fundamental network design problems in edge-weighted graphs: the group Steiner forest problem (thereby resolving an open question raised by Chekuri et. al. (SODA 2008)) and the single source ℓ-vertex connectivity problem (which complements similar results for the corresponding edge-connectivity problem due to Gupta et. al. (STOC 2009)).

In this paper, we introduce the semi-stochastic model for dealing with input uncertainty in optimization problems. This model is a hybrid between the overly pessimistic online model and the highly optimistic stochastic (or Bayesian) model. In this model, the algorithm can obtain only limited stochastic information about the future (i.e. about the input distribution)---as the amount of stochastic information we make available to the algorithm grows from no information to full information, we interpolate between the online and stochastic models. The central question in this framework is the trade-off between the performance of an algorithm, and the stochastic information that it can access. As a first step towards understanding this trade-off, we consider the ski-rental problem in the semi-stochastic setting. More precisely, given a desired competitive ratio, we give upper and lower bounds on the amount of stochastic information required by a deterministic algorithm for the ski-rental problem to achieve that competitive ratio.

Scientific workflow systems increasingly store provenance information about the module executions used to produce a data item, as well as the parameter settings and intermediate data items passed between module executions. However, authors/owners of workflows may wish to keep some of this information confidential. In particular, a module may be proprietary, and users should not be able to infer its behavior by seeing mappings between all data inputs and outputs.

Survivable network design is an important suite of algorithmic problems where the goal is to select a minimum cost network subject to the constraint that some desired connectivity property has to be satisfied by the network. Traditionally, these problems have been studied in a model where individual edges (and sometimes nodes) have an associated cost. This model does not faithfully represent wireless networks, where the activation of an edge is dependent on the selection of parameter values at its endpoints, and the cost incurred is a function of these values. We present a realistic optimization model for the design of survivable wireless networks that generalizes various connectivity problems studied in the theory literature, e.g. node-weighted steiner network, power optimization, minimum connected dominating set, and in the networking literature, e.g. installation cost optimization, minimum broadcast tree. We obtain the following algorithmic results for our general model: 1. For k = 1 and 2, we give O(log n)-approximation algorithms for both the vertex and edge connectivity versions of the k-connectivity problem. These results are tight (up to constants); we show that even for k = 1, it is NP-hard to obtain an approximation factor of o(log n). 2. For the minimum steiner network problem, we give a tight (up to constants) O(log n)-approximation algorithm. 3. We give a reduction from the k-edge connectivity problem to a more tractable degree-constrained problem. This involves proving new connectivity theorems that might be of independent interest. We apply this result to obtain new approximation algorithms in the power optimization and installation cost optimization applications.

We present a general framework for constructing cut sparsifiers in undirected graphs --- weighted subgraphs for which every cut has the same weight as the original graph, up to a multiplicative factor of (1 ε). Using this framework, we simplify, unify and improve upon previous sparsification results. As simple instantiations of this framework, we show that sparsifiers can be constructed by sampling edges according to their strength (a result of Benczur and Karger), effective resistance (a result of Spielman and Srivastava), edge connectivity, or by sampling random spanning trees. Sampling according to edge connectivity is the most aggressive method, and the most challenging to analyze. Our proof that this method produces sparsifiers resolves an open question of Benczur and Karger.

Commerce search engines have become popular in recent years, as users increasingly search for (and buy) products on the web. In response to an user query, they surface links to products in their catalog (or index) that match the requirements specified in the query. Often, few or no product in the catalog matches the user query exactly, and the search engine is forced to return a set of products that partially match the query. This paper considers the problem of choosing a set of products in response to an user query, so as to ensure maximum user satisfaction. We call this the result enrichment problem in commerce search.

In this paper, we study the theory of collaborative upload bandwidth measurement in peer-to-peer environments. A host can use a bandwidth estimation probe to determine the bandwidth between itself and any other host in the system. The problem is that the result of such a measurement may not necessarily be the sender's upload bandwidth, since the most bandwidth restricted link on the path could also be the receiver's download bandwidth. In this paper, we formally define the bandwidth determination problem and devise efficient distributed algorithms. We consider two models, the free-departure and no-departure model, depending on whether hosts keep participating in the algorithm even after their bandwidth has been determined. We present lower bounds on the time-complexity of any collaborative bandwidth measurement algorithm in both models. We then show how, for realistic bandwidth distributions, the lower bounds can be overcome. Specifically, we present O(1) and O(log log n)-time algorithms for the two models. We corroborate these theoretical findings with practical measurements on a implementation on PlanetLab.

Long-distance multi-hop wireless networks have been used in recent years to provide connectivity to rural areas. The salient features of such networks include TDMA channel access, nodes with multiple radios, and point-to-point long-distance wireless links established using high-gain directional antennas mounted on high towers. It has been demonstrated previously that in such network architectures, nodes can transmit concurrently on multiple radios, as well as receive concurrently on multiple radios. However, concurrent transmission on one radio, and reception on another radio causes interference. Under this scheduling constraint, given a set of source-destination demand rates, we consider the problem of satisfying the maximum fraction of each demand (also called the maximum concurrent flow problem). We give a novel joint routing and scheduling scheme for this problem, based on linear programming and graph coloring. We analyze our algorithm theoretically and prove that at least 50% of a satisfiable set of demands is satisfied by our algorithm for most practical networks (with maximum node degree at most 5).

ThunderDome is a system for collaboratively measuring upload bandwidths in ad-hoc peer-to-peer systems. It works by scheduling bandwidth probes between pairs of hosts, wherein each pairwise exchange reveals the upload constraint of one participant. Using the abstraction of bandwidth tournaments, unresolved hosts are successively paired with each other until every peer knows its upload bandwidth. To recover from measurement errors that corrupt its tournament schedule, ThunderDome aggregates multiple probe results for each host, avoiding pathological bandwidth estimations that would otherwise occur in systems with heterogeneous bandwidth distributions. For scalability, the coordination of probes is distributed across the hosts. Simulations on empirical and analytic bandwidth distributions--validated with wide-area PlanetLab experiments--show that ThunderDome efficiently yields upload bandwidth estimates that are robust to measurement error.

In the last few years, long-distance WiFi networks have been used to provide Internet connectivity in rural areas. The strong requirement to support real-time applications in these settings leads us to consider TDMA link scheduling. In this paper, we consider the FRACTEL architecture for long-distance mesh networks. We propose a novel angular interference model, which is not only practical, but also makes the problem of TDMA scheduling tractable. We then consider delay-bounded scheduling and present an algorithm which uses at most 1/3rd more time-slots than the optimal number of slots required without the delay bound. Our evaluation on various network topologies shows that the algorithm is practical, and more efficient in practice than its worst-case bound.

We define and study the bandwidth determination problem in ad-hoc P2P environments. Using point-to-point bandwidth probes, the goal is to quickly determine each host's upload and download bandwidth. We present matching upper and lower bounds on the number of probing rounds required by any algorithm. We also devise algorithms which, for realistic bandwidth distributions, beat the lower bounds.

We present an Õ(m) (near-linear) time Monte Carlo algorithm for constructing the cactus data structure, a useful representation of all the global minimum edge cuts of an undirected graph. Our algorithm represents a fundamental improvement over the best previous (quadratic time) algorithms: because there can be quadratically many min-cuts, our algorithm must avoid looking at all min-cuts during the construction, but nonetheless builds a data structure representing them all. Our result closes the gap between the (near-linear) time required to find a single min-cut and that for (implicitly) finding all the min-cuts.

In this paper we present a new channel allocation scheme for IEEE 802.11 based mesh networks with point-to- point links, designed for rural areas. Our channel allocation scheme allows continuous full-duplex data transfer on every link in the network. Moreover, we do not require any synchronization across the links as the channel assignment prevents cross link interference. Our approach is simple. We consider any link in the network as made up of two directed edges. To each directed edge at a node, we assign a non-interfering IEEE 802.11 channel so that the set of channels assigned to the outgoing edges is disjoint from channels assigned to the incoming edges. Evaluation of this scheme in a testbed demonstrate throughput gains of between 50 - 100%, and significantly less end-to-end delays, over existing link scheduling/channel allocation protocols (such as 2P [11]) designed for point-to-point mesh networks. Formally speaking, this channel allocation scheme is equivalent to an edge-coloring problem, that we call the directed edge coloring (DEC) problem. We establish a relationship between this coloring problem and the classical vertex coloring problem, and thus, show that this problem is NP-hard. More precisely, we give an algorithm that, given k vertex coloring of a graph can directed edge color it using xi(k) colors, where xi(k) is the smallest integer n such that (lfloorn/2rfloor/n ) ges k.

In this paper, we propose new "low-overhead" network monitoring techniques to detect violations of path-level QoS guarantees like end-to-end delay, loss, etc. Unlike existing path monitoring schemes, our approach does not calculate QoS parameters for all paths. Instead, it monitors QoS values for only a few paths, and exploits the fact that path anomalies are rare and anomalous states are well separated from normal operation, to rule out path QoS violations in most situations. We propose a heuristic to select a small subset of network paths to monitor while ensuring that no QoS violations are missed. Experiments with an ISP topology from the Rocketfuel data set show that our heuristic can deliver almost a 50% decrease in monitoring overhead compared to previous schemes.

IEEE 802.11 WiFi equipment based wireless mesh networks have recently been proposed as an inexpensive approach to connect far-flung rural areas. Such networks are built using high-gain directional antennas that can establish long-distance wireless point-to-point links. Some nodes in the network (called gateway nodes) are directly connected to the wired internet, and the remaining nodes connect to the gateway(s) using one or more hops. The dominant cost of constructing such a mesh network is the cost of constructing antenna towers at nodes. The cost of a tower depends on its height, which in turn depends on the length of its links and the physical obstructions along those links. We investigate the problem of selecting which links should be established such that all nodes are connected, while the cost of constructing the antenna towers required to establish the selected links is minimized. We show that this problem is NP-hard and that a better than O(log n) approximation cannot be expected, where n is the number of vertices in the graph. We then present the first algorithm in the literature, for this problem, with provable performance bounds. More precisely, we present a greedy algorithm that is an O(log n) approximation algorithm for this problem. Finally, through simulations, we compare our approximation algorithm with both the optimal solution, and a naive heuristic.

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V,E). The expected running time of our algorithm is Õ(mc) where |E| = m and c is the maximum u-vedge connectivity, where u,v ∈ V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n-1; so the expected running time of our algorithm for simple unweighted graphs is Õ(mn).