### Filter by type:

Sort by year:

#### The Itinerant List Update Problem

approximationConference
N. Olver, K. Pruhs, K. Schewior, R. Sitters and L. Stougie
Proceedings of the 16th Workshop on Approximation and Online Algorithms (WAOA)

#### Fast, Deterministic and Sparse Dimensionality Reduction

Conferenceprobability
Daniel Dadush, Cristóbal Guzman, Neil Olver
SODA 2018

#### Chain-constrained spanning trees

ConferenceJournalnetwork
Neil Olver and Rico Zenklusen
Mathematical Programming 167(2):293–314. Conference version in IPCO 2013.

We consider the problem of finding a spanning tree satisfying a family of additional constraints. Several settings have been considered previously, the most famous being the problem of finding a spanning tree with degree constraints. Since the problem is hard, the goal is typically to find a spanning tree that violates the constraints as little as possible.

Iterative rounding became the tool of choice for constrained spanning tree problems. However, iterative rounding approaches are very hard to adapt to settings where an edge can be part of a super-constant number of constraints. We consider a natural constrained spanning tree problem of this type, namely where upper bounds are imposed on a family of cuts forming a chain. Our approach reduces the problem to a family of independent matroid intersection problems, leading to a spanning tree that violates each constraint by a factor of at most 9.

We also present strong hardness results: among other implications, these are the first to show, in the setting of a basic constrained spanning tree problem, a qualitative difference between what can be achieved when allowing multiplicative as opposed to additive constraint violations.

#### On the Integrality Gap of the Prize-Collecting Steiner Forest LP

approximationConferencenetwork
Jochen Koenemann, Kanstantsin Pashkovich, Neil Olver, R. Ravi, Chaitanya Swamy, Jens Vygen
Accepted to APPROX 2017

#### Long term behavior of dynamic equilibria in fluid queuing networks

agtConference
Roberto Comminetti, Jose Correa and Neil Olver
Accepted to IPCO 2017

#### Exploring the tractability of the capped hose model

Conferencenetwork
Thomas Bosman, Neil Olver
Proceedings of the 25th Annual European Symposium on Algorithms (ESA)

#### A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization

Conferencenetwork
Neil Olver and László Végh
Accepted to STOC 2017

We present a new strongly polynomial algorithm for generalized flow maximization. The first strongly polynomial algorithm for this problem was given in [Végh 2016]; 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 in [ Végh 2016] 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 for the problem.

#### On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree

ConferenceJournalnetwork
Andreas E. Feldmann, Jochen Koenemann, Neil Olver and Laura Sanità
Mathematical Programming 160:379-406. Conference version: APPROX 2014

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.

Conferenceprobability
José Correa, Marcos Kiwi , Neil Olver and Alberto Vera
WINE 2015

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.

#### Decentralized utilitarian mechanisms for scheduling games

agtConferenceJournal
R. Cole, J. Correa, V. Gkatzelis, V. Mirrokni and N. Olver
Games and Economic Behavior, Volume 92, pp 306–326, 2015. Conference version: STOC 2011

Game Theory and Mechanism Design are by now standard tools for studying and designing massive decentralized systems. Unfortunately, designing mechanisms that induce socially efficient outcomes often requires full information and prohibitively large computational resources. In this work we study simple mechanisms that require only local information. Specifically, in the setting of a classic scheduling problem, we demonstrate local mechanisms that induce outcomes with social cost close to that of the socially optimal solution. Somewhat counter-intuitively, we find that mechanisms yielding Pareto dominated outcomes may in fact enhance the overall performance of the system, and we provide a justification of these results by interpreting these inefficiencies as externalities being internalized. We also show how to employ randomization to obtain yet further improvements. Lastly, we use the game-theoretic insights gained to obtain a new combinatorial approximation algorithm for the underlying optimization problem.

#### Pipage Rounding, Pessimistic Estimators and Matrix Concentration

Conferenceprobability
N. Harvey, N. Olver
SODA 2014

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 $\kappa$, returns an $O(\kappa^{-1} \cdot \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.

#### Approximability of robust network design

approximationConferenceJournalnetwork
Neil Olver and Bruce Shepherd
Mathematics of Operations Research 39(2):561–572, 2014. Conference version: SODA 2010

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 (2003), generalizes the well studied virtual private network (VPN) problem. Most research in this area has focused on ﬁnding constant factor approximations for speciﬁc polytope of demands, such as the class of hose matrices used in the deﬁnition of VPN. As pointed out in Chekuri (2007), 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 logarithmic 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.

#### The VPN Conjecture is true

ConferenceJournalnetwork
Navin Goyal, Neil Olver and Bruce Shepherd
Journal of the ACM, 60(3), 2013. Conference version: STOC 2008

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$, $\sum_{j \neq i} D_{ij} \leq 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 \in 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 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 et al. 2005, Grandoni et al. 2007, Fiorini et al. 2007). Our main theorem establishes that this conjecture is true in general graphs. This proves that the single path VPN problem is solvable in polynomial time. We also show that the multipath version of the conjecture is false.

#### Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations

Conferencenetwork
Michel Goemans, Neil Olver, Thomas Rothvoss and Rico Zenklusen
STOC 2012

Until recently, LP relaxations have played a limited role in the design of approximation algorithms for the Steiner tree problem. In 2010, Byrka et al. presented a ln(4)+epsilon approximation based on a hypergraphic LP relaxation, but surprisingly, their analysis does not provide a matching bound on the integrality gap.
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, we present a deterministic ln(4)+epsilon approximation that compares against the LP value and therefore proves a matching ln(4) upper bound on the integrality gap.
Similarly to Byrka et al., we iteratively fix one component and update the LP solution. However, whereas they solve an LP at every iteration after contracting a component, we show how feasibility can be maintained by a greedy procedure on a well-chosen matroid. Apart from avoiding the expensive step of solving a hypergraphic LP at each iteration, our algorithm can be analyzed using a simple potential function. This gives an easy means to determine stronger approximation guarantees and integrality gaps when considering restricted graph topologies. In particular, this readily leads to a 73/60 bound on the integrality gap for quasi-bipartite graphs.
For the case of quasi-bipartite graphs, we present a simple algorithm to transform an optimal solution to the bidirected cut relaxation to an optimal solution of the hypergraphic relaxation, leading to a fast 73/60 approximation for quasi-bipartite graphs. Furthermore, we show how the separation problem of the hypergraphic relaxation can be solved by computing maximum flows, providing a fast independence oracle for our matroids.

#### Dynamic vs Oblivious Routing in Network Design

ConferenceJournalnetwork
Navin Goyal, Neil Olver and Bruce Shepherd
Algorithmica 61(1): 161–173, 2011. Conference version: ESA 2009

Consider the robust network design problem of finding a minimum cost network with enough capacity to route all traffic demand matrices in a given polytope. We investigate the impact of different routing models in this robust setting: in particular, we compare oblivious routing, where the routing between each terminal pair must be fixed in advance, to dynamic routing, where routings may depend arbitrarily on the current demand. Our main result is a construction that shows that the optimal cost of such a network based on oblivious routing (fractional or integral) may be a factor of $\Omega(\log{n})$ more than the cost required when using dynamic routing. This is true even in the important special case of the asymmetric hose model. This answers a question in Chekuri (2007), and is tight up to constant factors. Our proof technique builds on a connection between expander graphs and robust design for single-sink traffic patterns (Chekuri et al. 2007).