The strong thin tree conjecture states that every k-edge-connected graph G contains an O(1/k)-thin spanning tree, meaning a spanning tree which contains at most an O(1/k) fraction of the edges across each cut in G. This conjecture is still open despite significant effort; the best current result by Anari and Oveis Gharan shows the existence of an O(polylog log n/k)-thin tree. In this work, we demonstrate that the conjecture is true if one only requires thinness for the set of η-near minimum cuts of the graph for η = 1/40, in other words, for the set of cuts with fewer than (1+1/40)k edges. Our approach constructs such a tree in polynomial time. To show this, we utilize the structure of near minimum cuts, and in particular the polygon representation of Benczúr and Goemans, to reduce to the previously solved problem of finding a spanning tree that is O(1/k)-thin for all sets in a laminar family.

In the nonuniform graph partitioning problem, we are given a capacitated graph G on n vertices, and numbers n1, n2, …, nk summing to n. The goal is to partition the vertices of G into parts S1, S2, …, Sk with |Si| = ni for each i, and minimizing the capacity of edges crossing between distinct parts. This generalizes, for instance, the well-known graph bisection problem.

Emerging optical switching technologies enable demand-aware datacenter networks, whose topology can be flexibly optimized toward the traffic they serve. This paper revisits the bounded-degree network design problem underlying such demand-aware networks. Namely, given a distribution over communicating node pairs (represented has a demand graph), we want to design a network with bounded maximum degree (called host graph) that minimizes the expected communication distance. We improve the understanding of this problem domain by filling several gaps in prior work. First, we present the first practical algorithm for solving this problem on arbitrary instances without violating the degree bound. Our algorithm is based on novel insights obtained from studying a new Steiner node version of the problem, and we report on an extensive empirical evaluation, using several real-world traffic traces from datacenters, finding that our approach results in improved demand-aware network designs. Second, we shed light on the complexity and hardness of the bounded-degree network design problem by formally establishing its NP-completeness for any degree. We use our techniques to improve prior upper bounds for sparse instances. Finally, we study an intriguing connection between demand-aware network design and the virtual networking embedding problem, and show that the latter cannot be used to approximate the former: there is no universal host graph which can provide a constant approximation for our problem.

We give a strongly polynomial algorithm for minimum cost generalized flow, and hence for optimizing any linear program with at most two non-zero entries per row, or at most two non-zero entries per column. Primal and dual feasibility were shown by Végh ‍(MOR ’17) and Megiddo ‍(SICOMP ’83), respectively. Our result can be viewed as progress towards understanding whether all linear programs can be solved in strongly polynomial time, also referred to as Smale’s 9th problem. Our approach is based on the recent primal-dual interior point method (IPM) by Allamigeon, Dadush, Loho, Natura, and Végh ‍(FOCS ’22). The number of iterations needed by the IPM is bounded, up to a polynomial factor in the number of inequalities, by the straight line complexity of the central path. Roughly speaking, this is the minimum number of pieces of any piecewise linear curve that multiplicatively approximates the central path. As our main contribution, we show that the straight line complexity of any minimum cost generalized flow instance is polynomial in the number of arcs and vertices. By applying a reduction of Hochbaum ‍(ORL ’04), the same bound applies to any linear program with at most two non-zeros per column or per row. To be able to run the IPM, one requires a suitable initial point. For this purpose, we develop a novel multistage approach, where each stage can be solved in strongly polynomial time given the result of the previous stage. Beyond this, substantial work is needed to ensure that the bit complexity of each iterate remains bounded during the execution of the algorithm. For this purpose, we show that one can maintain a representation of the iterates as a low complexity convex combination of vertices and extreme rays. Our approach is black-box and can be applied to any log-barrier path-following method.

In the laminar-constrained spanning tree problem, the goal is to find a minimum-cost spanning tree which respects upper bounds on the number of times each cut in a given laminar family is crossed. This generalizes the well-studied degree-bounded spanning tree problem, as well as a previously studied setting where a chain of cuts is given. We give the first constant-factor approximation algorithm; in particular we show how to obtain a multiplicative violation of the crossing bounds of less than 22 while losing less than a factor of 5 in terms of cost. Our result compares to the natural $L P$ relaxation. As a consequence, our results show that given a k-edge-connected graph and a laminar family $\mathcal{L} \subseteq 2^{V}$ of cuts, there exists a spanning tree which contains only an $O(1 / k)$ fraction of the edges across every cut in $\mathcal{L}$. This can be viewed as progress towards the Thin Tree Conjecture, which (in a strong form) states that this guarantee can be obtained for all cuts simultaneously.

We consider a dynamic model of traffic that has received a lot of attention in the past few years. Infinitesimally small agents aim to travel from a source to a destination as quickly as possible. Flow patterns vary over time, and congestion effects are modeled via queues, which form based on the deterministic queueing model whenever the inflow into a link exceeds its capacity.Are equilibria in this model meaningful as a prediction of traffic behavior? For this to be the case, a certain notion of stability under ongoing perturbations is needed. Real traffic consists of discrete, atomic “packets”, rather than being a continuous flow of non-atomic agents. Users may not choose an absolutely quickest route available, if there are multiple routes with very similar travel times. We would hope that in both these situations - a discrete packet model, with packet size going to 0, and $\varepsilon$-equilibria, with $\varepsilon$ - going to 0 - equilibria converge to dynamic equilibria in the flow over time model. No such convergence results were known.We show that such a convergence result does hold in single-commodity instances for both of these settings, in a unified way. More precisely, we introduce a notion of “strict” $\varepsilon$-equilibria, and show that these must converge to the exact dynamic equilibrium in the limit as $\varepsilon \rightarrow 0$. We then show that results for the two settings mentioned can be deduced from this with only moderate further technical effort.

We consider a dynamic model of traffic that has received a lot of attention in the past few years. Users control infinitesimal flow particles aiming to travel from a source to destination as quickly as possible. Flow patterns vary over time, and congestion effects are modeled via queues, which form whenever the inflow into a link exceeds its capacity. Despite lots of interest, some very basic questions remain open in this model. We resolve a number of them: • We show uniqueness of journey times in equilibria. • We show continuity of equilibria: small perturbations to the instance or to the traffic situation at some moment cannot lead to wildly different equilibrium evolutions. • We demonstrate that, assuming constant inflow into the network at the source, equilibria always settle down into a “steady state” in which the behavior extends forever in a linear fashion. One of our main conceptual contributions is to show that the answer to the first two questions, on uniqueness and continuity, are intimately connected to the third. Our result also shows very clearly that resolving uniqueness and continuity, despite initial appearances, cannot be resolved by analytic techniques, but are related to very combinatorial aspects of the model. To resolve the third question, we substantially extend the approach of Cominetti et al. [1], who show a steady-state result in the regime where the input flow rate is smaller than the network capacity. The full version of this extended abstract can be found on the arXiv preprint server as article 2111.06877

The theory of majorizing measures, extensively developed by Fernique, Talagrand and many others, provides one of the most general frameworks for controlling the behavior of stochastic processes. In particular, it can be applied to derive quantitative bounds on the expected suprema and the degree of continuity of sample paths for many processes. One of the crowning achievements of the theory is Talagrand’s tight alternative characterization of the suprema of Gaussian processes in terms of majorizing measures. The proof of this theorem was difficult, and thus considerable effort was put into the task of developing both shorter and easier to understand proofs. A major reason for this difficulty was considered to be theory of majorizing measures itself, which had the reputation of being opaque and mysterious. As a consequence, most recent treatments of the theory (including by Talagrand himself) have eschewed the use of majorizing measures in favor of a purely combinatorial approach (the generic chaining) where objects based on sequences of partitions provide roughly matching upper and lower bounds on the desired expected supremum. In this paper, we return to majorizing measures as a primary object of study, and give a viewpoint that we think is natural and clarifying from an optimization perspective. As our main contribution, we give an algorithmic proof of the majorizing measures theorem based on two parts: We make the simple (but apparently new) observation that finding the best majorizing measure can be cast as a convex program. This also allows for efficiently computing the measure using off-the-shelf methods from convex optimization. We obtain tree-based upper and lower bound certificates by rounding, in a series of steps, the primal and dual solutions to this convex program. While duality has conceptually been part of the theory since its beginnings, as far as we are aware no explicit link to convex optimization has been previously made.

Abstract Flows over time have received substantial attention from both an optimization and (more recently) a game-theoretic perspective. In this model, each arc has an associated delay for traversing the arc, and a bound on the rate of flow entering the arc; flows are time-varying. We consider a setting which is very standard within the transportation economic literature, but has received little attention from an algorithmic perspective. The flow consists of users who are able to choose their route but also their departure time, and who desire to arrive at their destination at a particular time, incurring a scheduling cost if they arrive earlier or later. The total cost of a user is then a combination of the time they spend commuting, and the scheduling cost they incur. We present a combinatorial algorithm for the natural optimization problem, that of minimizing the average total cost of all users (i.e., maximizing the social welfare). Based on this, we also show how to set tolls so that this optimal flow is induced as an equilibrium of the underlying game.

We present a new strongly polynomial algorithm for generalized flow maximization that is significantly simpler and faster than the previous strongly polynomial algorithm [34]. For the uncapacitated problem formulation, the complexity bound O ( mn ( m + n log n )log ( n 2 / m )) improves on the previous estimate by almost a factor O ( n 2 ). Even for small numerical parameter values, our running time bound is comparable to the best weakly polynomial algorithms. The key new technical idea is relaxing the primal feasibility conditions. This allows us to work almost exclusively with integral flows, in contrast to all previous algorithms for the problem.

We provide a deterministic construction of the sparse Johnson-Lindenstrauss transform of Kane & Nelson (J.ACM 2014) which runs, under a mild restriction, in the time necessary to apply the sparse embedding matrix to the input vectors.Specifically, given a set of n vectors in R d and target error ε, we give a deterministic algorithm to compute a {-1, 0, 1} embedding matrix of rank O((ln n)/ε 2 ) with O((ln n)/ε) entries per column which preserves the norms of the vectors to within 1±ε.If NNZ, the number of non-zero entries in the input set of vectors, is Ω(d 2 ), our algorithm runs in time O(NNZ • ln n/ε).One ingredient in our construction is an extremely simple proof of the Hanson-Wright inequality for subgaussian random variables, which is more amenable to derandomization.As an interesting byproduct, we are able to derive the essentially optimal form of the inequality in terms of its functional dependence on the parameters.

In the prize-collecting Steiner forest (PCSF) problem, we are given an undirected graph G=(V,E), nonnegative edge costs {c_e} for e in E, terminal pairs {(s_i,t_i)} for i=1,...,k, and penalties {pi_i} for i=1,...,k for each terminal pair; the goal is to find a forest F to minimize c(F) + sum{ pi_i: (s_i,t_i) is not connected in F }. The Steiner forest problem can be viewed as the special case where pi_i are infinite for all i. It was widely believed that the integrality gap of the natural (and well-studied) linear-programming (LP) relaxation for PCSF (PCSF-LP) is at most 2. We dispel this belief by showing that the integrality gap of this LP is at least 9/4 even if the input instance is planar. We also show that using this LP, one cannot devise a Lagrangian-multiplier-preserving (LMP) algorithm with approximation guarantee better than 4. Our results thus show a separation between the integrality gaps of the LP-relaxations for prize-collecting and non-prize-collecting (i.e., standard) Steiner forest, as well as the approximation ratios achievable relative to the optimal LP solution by LMP- and non-LMP-approximation algorithms for PCSF. For the special case of prize-collecting Steiner tree (PCST), we prove that the natural LP relaxation admits basic feasible solutions with all coordinates of value at most 1/3 and all edge variables positive. Thus, we rule out the possibility of approximating PCST with guarantee better than 3 using a direct iterative rounding method.

Robust network design concerns the design of networks to support uncertain or varying traffic patterns. An especially important case is the VPN problem, where the total traffic emanating from any node is bounded, but there are no further constraints on the traffic pattern. Recently, Fréchette et al. [INFOCOM, 2013] studied a generalization of the VPN problem where in addition to these so-called hose constraints, there are individual upper bounds on the demands between pairs of nodes. They motivate their model, give some theoretical results, and propose a heuristic algorithm that performs well on real-world instances. Our theoretical understanding of this model is limited; it is APX-hard in general, but tractable when either the hose constraints or the individual demand bounds are redundant. In this work, we uncover further tractable cases of this model; our main result concerns the case where each terminal needs to communicate only with two others. Our algorithms all involve optimally embedding a certain auxiliary graph into the network, and have a connection to a heuristic suggested by Fréchette et al. for the capped hose model in general.

We present a new strongly polynomial algorithm for generalized flow maximization. The first strongly polynomial algorithm for this problem was given very recently by Végh; our new algorithm is much simpler, and much faster. The complexity bound O((m+nlogn)mnlog(n2/m)) improves on the previous estimate obtained by Végh by almost a factor O(n2). Even for small numerical parameter values, our algorithm is essentially as fast as the best weakly polynomial algorithms. The key new technical idea is relaxing primal feasibility conditions. This allows us to work almost exclusively with integral flows, in contrast to all previous algorithms.

Motivated by the recent emergence of the so-called opportunistic communication networks, we consider the issue of adaptivity in the most basic continuous time (asynchronous) rumor spreading process. In our setting a rumor has to be spread to a population; the service provider can push it at any time to any node in the network and has unit cost for doing this. On the other hand, as usual in rumor spreading, nodes share the rumor upon meeting and this imposes no cost on the service provider. Rather than fixing a budget on the number of pushes, we consider the cost version of the problem with a fixed deadline and ask for a minimum cost strategy that spreads the rumor to every node. A non-adaptive strategy can only intervene at the beginning and at the end, while an adaptive strategy has full knowledge and intervention capabilities. Our main result is that in the homogeneous case (where every pair of nodes randomly meet at the same rate) the benefit of adaptivity is bounded by a constant. This requires a subtle analysis of the underlying random process that is of interest in its own right. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

The bottleneck of the currently best (ln(4) + epsilon)-approximation algorithm for the NP-hard Steiner tree problem is the solution of its large, so called hypergraphic, linear programming relaxation (HYP). Hypergraphic LPs are NP-hard to solve exactly, and it is a formidable computational task to even approximate them sufficiently well. We focus on another well-studied but poorly understood LP relaxation of the problem: the bidirected cut relaxation (BCR). This LP is compact, and can therefore be solved efficiently. Its integrality gap is known to be greater than 1.16, and while this is widely conjectured to be close to the real answer, only a (trivial) upper bound of 2 is known. In this paper, we give an efficient constructive proof that BCR and HYP are polyhedrally equivalent in instances that do not have an (edge-induced) claw on Steiner vertices, i.e., they do not contain a Steiner vertex with 3 Steiner neighbors. This implies faster ln(4)-approximations for these graphs, and is a significant step forward from the previously known equivalence for (so called quasi-bipartite) instances in which Steiner vertices form an independent set. We complement our results by showing that even restricting to instances where Steiner vertices induce one single star, determining whether the two relaxations are equivalent is NP-hard.

Pipage rounding is a dependent random sampling technique that has several interesting properties and diverse applications. One property that has been useful in applications is negative correlation of the resulting vector. There are some further properties that would be interesting to derive, but do not seem to follow from negative correlation. In particular, recent concentration results for sums of independent random matrices are not known to extend to a negatively dependent setting. We introduce a simple but useful technique called concavity of pessimistic estimators. This technique allows us to show concentration of submodular functions and concentration of matrix sums under pipage rounding. The former result answers a question of Chekuri et al. (2009). To prove the latter result, we derive a new variant of Lieb's celebrated concavity theorem in matrix analysis. We provide numerous applications of these results. One is to spectrally-thin trees, a spectral analog of the thin trees that played a crucial role in the recent breakthrough on the asymmetric traveling salesman problem. We show a polynomial time algorithm that, given a graph where every edge has effective conductance at least κ, returns an O(κ−1 · log n/log log n)-spectrally-thin tree. There are further applications to rounding of semidefinite programs and to a geometric question of extracting a nearly-orthonormal basis from an isotropic distribution.

We consider the following network design problem. We are given an undirected graph G = ( V , E ) with edge costs c ( e ) and a set of terminal nodes W ⊆ V . A hose demand matrix is any symmetric matrix D , indexed by the terminals, such that for each i ∈ W , ∑ j≠i D ij ≤ 1. We must compute the minimum-cost edge capacities that are able to support the oblivious routing of every hose matrix in the network. An oblivious routing template, in this context, is a simple path P ij for each pair i,j ∈ W . Given such a template, if we are to route a demand matrix D , then for each i,j , we send D ij units of flow along each P ij . Fingerhut et al. [1997] and Gupta et al. [2001] obtained a 2-approximation for this problem, using a solution template in the form of a tree. It has been widely asked and subsequently conjectured [Italiano et al. 2006] that this solution actually results in the optimal capacity for the single-path VPN design problem; this has become known as the VPN Conjecture . The conjecture has previously been proven for some restricted classes of graphs [Fingerhut et al. 1997; Fiorini et al. 2007; Grandoni et al. 2008; Hurkens et al. 2007]. Our main theorem establishes that this conjecture is true in general graphs. This also has the implication that the single-path VPN problem is solvable in polynomial time. A natural fractional version of the conjecture had also been proposed [Hurkens et al. 2007]. In this version, the routing may split flow between many paths, in specified proportions. We demonstrate that this multipath version of the conjecture is in fact false. The multipath and single path versions of the VPN problem are essentially direct analogues of the randomized and nonrandomized versions of oblivious routing schemes for minimizing congestion for permutation routing [Borodin and Hopcroft 1982; Valiant 1982].

Until recently, LP relaxations have only played a very limited role in the design of approximation algorithms for the Steiner tree problem. In particular, no (efficiently solvable) Steiner tree relaxation was known to have an integrality gap bounded away from 2, before Byrka et al. [3] showed an upper bound of ~1.55 of a hypergraphic LP relaxation and presented a ln(4)+ε ~1.39 approximation based on this relaxation. Interestingly, even though their approach is LP based, they do not compare the solution produced against the LP value. We take a fresh look at hypergraphic LP relaxations for the Steiner tree problem---one that heavily exploits methods and results from the theory of matroids and submodular functions---which leads to stronger integrality gaps, faster algorithms, and a variety of structural insights of independent interest. More precisely, along the lines of the algorithm of Byrka et al.[3], we present a deterministic ln(4)+ε approximation that compares against the LP value and therefore proves a matching ln(4) upper bound on the integrality gap of hypergraphic relaxations.

We study coordination mechanisms aiming to minimize the weighted sum of completion times of jobs in the context of selfish scheduling problems. Our goal is to design local policies that achieve a good price of anarchy in the resulting equilibria for unrelated machine scheduling. To obtain these approximation bounds, we introduce a new technique that while conceptually simple, seems to be quite powerful. The method entails mapping strategy vectors into a carefully chosen inner product space; costs are shown to correspond to the norm in this space, and the Nash condition also has a simple description. With this structure in place, we are able to prove a number of results, as follows. First, we consider Smith's Rule, which orders the jobs on a machine in ascending processing time to weight ratio, and show that it achieves an approximation ratio of 4. We also demonstrate that this is the best possible for deterministic non-preemptive strongly local policies. Since Smith's Rule is always optimal for a given fixed assignment, this may seem unsurprising, but we then show that better approximation ratios can be obtained if either preemption or randomization is allowed.

We consider robust network design problems where the set of feasible demands may be given by an arbitrary polytope or convex body more generally. This model, introduced by Ben-Ameur and Kerivin [2], generalizes the well studied virtual private network (VPN) problem. Most research in this area has focused on finding constant factor approximations for specific polytope of demands, such as the class of hose matrices used in the definition of VPN. As pointed out in [4], however, the general problem was only known to be APX-hard (based on a reduction from the Steiner tree problem). We show that the general robust design is hard to approximate to within polylogarithmic factors. We establish this by showing a general reduction of buy-at-bulk network design to the robust network design problem. In the second part of the paper, we introduce a natural generalization of the VPN problem. In this model, the set of feasible demands is determined by a tree with edge capacities; a demand matrix is feasible if it can be routed on the tree. We give a constant factor approximation algorithm for this problem that achieves factor 8 in general, and 2 for the case where the tree has unit capacities.

We consider the following network design problem. We are given an undirected graph G=(V,E) with edges costs c(e) and a set of terminal nodes W. A hose demand matrix for W is any symmetric matrix [Dij] such that for each i, ∑ j ≠ i Dij ≤ 1. We must compute the minimum cost edge capacities that are able to support the oblivious routing of every hose matrix in the network.