Neil Olver

Neil Olver

Auto-generated profile, based on publicly available information

Neil Olver

London School of Economics and Political Science, London, United Kingdom

Research Focus & Metrics

Academic Career Length

20Years (2007-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 July 2015 in Games and Economic Behavior
Verified
Journal Article
Closed access
RCRichard Cole
Richard Cole
JCJosé R. Correa
José R. Correa
VGVasilis Gkatzelis
Vasilis Gkatzelis
VMVahab Mirrokni
Vahab Mirrokni
NONeil Olver
Neil Olver

1 May 2013 in The Annals of Probability
Verified
Journal Article
Open access
OAOmid Amini
Omid Amini
LDLuc Devroye
Luc Devroye
SGSimon Griffiths
Simon Griffiths
NONeil Olver
Neil Olver
Consider a branching random walk on $\mathbb{R}$, with offspring distribution $Z$ and nonnegative displacement distribution $W$. We say that explosion occurs if an infinite number of particles may be found within a finite distance of the origin. In this paper, we investigate this phenomenon when the offspring distribution $Z$ is heavy-tailed. Under an appropriate condition, we are able to characterize the pairs $(Z,W)$ for which explosion occurs, by demonstrating the equivalence of explosion with a seemingly much weaker event: that the sum over generations of the minimum displacement in each generation is finite. Furthermore, we demonstrate that our condition on the tail is best possible for this equivalence to occur. We also investigate, under additional smoothness assumptions, the behavior of $M_{n}$, the position of the particle in generation $n$ closest to the origin, when explosion does not occur (and hence $\lim_{n\rightarrow\infty}M_{n}=\infty$).

19 May 2012
Verified
Conference Paper
Open access
PDF file
MGMichel X. Goemans
Michel X. Goemans
NONeil Olver
Neil Olver
TRThomas Rothvoß
Thomas Rothvoß
RZRico Zenklusen
Rico Zenklusen
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. Similarly to [3], we iteratively fix one component and update the LP solution. However, whereas in [3] the LP is solved 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 potential function 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 ~1.217 upper bound on the integrality gap of hypergraphic relaxations for quasi-bipartite graphs. Additionally, 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, which provides a way to obtain a fast independence oracle for the matroids that we use in our approach.Original manuscript December 13, 2011National Science Foundation (U.S.) (Grant CCF-1115849)National Science Foundation (U.S.) (Grant CCF-0829878)United States. Office of Naval Research (Grant N00014-11-1-0053)United States. Office of Naval Research (Grant N00014-09-1-0326

18 February 2016 in Mathematical Programming
Verified
Journal Article
Open access
PDF file
AFAndreas Emil Feldmann
Andreas Emil Feldmann
JKJochen Könemann
Jochen Könemann
NONeil Olver
Neil Olver
LSLaura Sanità
Laura Sanità
The bottleneck of the currently best \((\ln (4)+{\varepsilon })\)-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 strongly 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 article, 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 three Steiner neighbours. 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.

6 June 2011
Verified
Conference Paper
Open access
RCRichard Cole
Richard Cole
JCJosé R. Correa
José R. Correa
VGVasilis Gkatzelis
Vasilis Gkatzelis
VMVahab Mirrokni
Vahab Mirrokni
NONeil Olver
Neil Olver

17 April 2020 in Journal of the ACM
Verified
Journal Article
Open access
NONeil Olver
Neil Olver
LVLászló A. Végh
László A. Végh
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.