Neil Olver

STOC Conference 2024 Conference Paper

A Strongly Polynomial Algorithm for Linear Programs with At Most Two Nonzero Entries per Row or Column

• Daniel Dadush
• Zhuan Khye Koh
• Bento Natura
• Neil Olver
• László A. Végh

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.

FOCS Conference 2023 Conference Paper

Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time

• Neil Olver
• Leon Sering
• Laura Vargas Koch

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.

FOCS Conference 2023 Conference Paper

Thin Trees for Laminar Families

• Nathan Klein
• Neil Olver

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.

FOCS Conference 2021 Conference Paper

Continuity, Uniqueness and Long-Term Behavior of Nash Flows Over Time

• Neil Olver
• Leon Sering
• Laura Vargas Koch

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

SODA Conference 2018 Conference Paper

Fast, Deterministic and Sparse Dimensionality Reduction

• Daniel Dadush
• Cristóbal Guzmán
• Neil Olver

STOC Conference 2017 Conference Paper

A simpler and faster strongly polynomial algorithm for generalized flow maximization

• Neil Olver
• László A. Végh

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 + n log n ) mn log( n 2 / m )) improves on the previous estimate obtained by Végh by almost a factor O ( n 2 ). 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.

SODA Conference 2014 Conference Paper

Pipage Rounding, Pessimistic Estimators and Matrix Concentration

• Nicholas J. A. Harvey
• Neil Olver

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.

STOC Conference 2012 Conference Paper

Matroids and integrality gaps for hypergraphic steiner tree relaxations

• Michel X. Goemans
• Neil Olver
• Thomas Rothvoss
• Rico Zenklusen

STOC Conference 2011 Conference Paper

Inner product spaces for MinSum coordination mechanisms

• Richard Cole 0001
• José Correa 0001
• Vasilis Gkatzelis
• Vahab Mirrokni
• Neil Olver

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 prove that ProportionalSharing, a preemptive strongly local policy, achieves an approximation ratio of 2.618 for the weighted sum of completion times, and an approximation ratio of 2.5 in the unweighted case. We also observe that these bounds are tight. Next, we consider Rand, a natural non-preemptive but randomized policy. We show that it achieves an approximation ratio of at most 2.13; moreover, if the sum of the weighted completion times is negligible compared to the cost of the optimal solution, this improves to π/2. Finally, we show that both ProportionalSharing and Rand induce potential games, and thus always have a pure Nash equilibrium (unlike Smith's Rule). This allows us to design the first combinatorial constant-factor approximation algorithm minimizing weighted completion time for unrelated machine scheduling. It achieves a factor of 2+ε for any ε > 0, and involves imitating best response dynamics using a variant of ProportionalSharing as the policy.

SODA Conference 2010 Conference Paper

Approximability of Robust Network Design

• Neil Olver
• F. Bruce Shepherd

STOC Conference 2008 Conference Paper

The vpn conjecture is true

• Navin Goyal
• Neil Olver
• F. Bruce Shepherd

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 [D ij ] such that for each i, ∑ 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. and Gupta et al. 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 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 [Hurkens 2005, Grandoni 2007, Fiorini 2007]. Our main theorem establishes that this conjecture is true in general graphs. This also gives the first polynomial time algorithm for the single path VPN problem. We also show that the multipath version of the conjecture is false.