Publications

• Thin Trees for Near Minimum Cuts
  Nathan Klein, Neil Olver and Zi Song Yeoh
  Proceedings of the 53rd EATCS International Colloquium on Automata, Languages, and Programming (ICALP), 2026
  Accepted
  networksapproximation
• Stochastic Load Balancing with Machine Reservations
  David Aleman Espinosa, Naveen Garg, Sharat Ibrahimpur, Neil Olver and Chaitanya Swamy
  Proceedings of the 27th Conference on Integer Programming and Combinatorial Optimization (IPCO), 2026
  Accepted
  schedulingprobability
• Nonuniform Graph Partitioning with Just a Little Flex
  Neil Olver, Harald Räcke and Stefan Schmid
  Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC), 2026
  Accepted
  networksapproximation
• Continuity, Uniqueness and Long-Term Behavior of Nash Flows Over Time arXiv
  Neil Olver, Leon Sering and Laura Vargas Koch
  Operations Research, 2026
  Conference version: Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2021
  flowgame theory
• Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time arXiv
  Neil Olver, Leon Sering and Laura Vargas Koch
  Journal of the ACM, 2026
  Conference version: Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 123–133, 2023
  flowgame theory
• 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 and László Végh
  Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pp. 1561–1572, 2024
  flowoptimization
• Efficient Algorithms for Demand-Aware Networks and a Connection to Virtual Network Embedding arXiv
  Aleksander Figiel, Janne H. Korhonen, Neil Olver and Stefan Schmid
  Proceedings of the 28th International Conference on Principles of Distributed Systems (OPODIS), pp. 38:1–38:24, 2024
  networks
• Thin Trees for Laminar Families arXiv
  Nathan Klein and Neil Olver
  Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 50–50, 2023
  Minor revisions for SIAM Journal on Computing
  networksapproximation
• Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time arXiv
  Neil Olver, Leon Sering and Laura Vargas Koch
  Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 123–133, 2023
  flowgame theory
• A Duality-Based 2-Approximation Algorithm for Maximum Agreement Forest arXiv
  Neil Olver, Frans Schalekamp, Suzanne van der Ster, Leen Stougie and Anke van Zuylen
  Mathematical Programming, 2022
  approximation
• Long Term Behavior of Dynamic Equilibria in Fluid Queuing Networks arXiv
  Roberto Cominetti, José Correa and Neil Olver
  Operations Research, 70(1), 2022
  Conference version: Proceedings of the 19th Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 161–172, 2017
  flowgame theory
• Continuity, Uniqueness and Long-Term Behavior of Nash Flows Over Time arXiv
  Neil Olver, Leon Sering and Laura Vargas Koch
  Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2021
  flowgame theory
• Algorithms for Flows Over Time with Scheduling Costs arXiv
  Dario Frascaria and Neil Olver
  Mathematical Programming, 192:177–206, 2021
  Conference version: Proceedings of the 21st Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 130–143, 2020
  flowscheduling
• Majorizing Measures for the Optimizer
  Sem Borst, Daniel Dadush, Neil Olver and Makrand Sinha
  Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS), 2021
  probabilityoptimization
• A Short Proof of Convexity of Step-Out–Step-In Sequencing Games
  Cameron Beeson and Neil Olver
  Operations Research Letters, 49(2):257–259, 2021
  game theoryscheduling
• Emergent Hypercongestion in Vickrey Bottleneck Networks
  Dario Frascaria, Neil Olver and Erik Verhoef
  Transportation Research Part B, 139:523–529, 2020
  flowgame theory
• Performance of the Smallest-Variance-First Rule in Appointment Scheduling arXiv
  Madelon de Kemp, Michel Mandjes and Neil Olver
  Operations Research, 69(6):1909–1935, 2020
  schedulingprobability
• A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization arXiv
  Neil Olver and László Végh
  Journal of the ACM, 67(2), 2020
  Conference version: Proceedings of the 49th ACM Symposium on Theory of Computing (STOC), pp. 100–111, 2017
  flowoptimization
• Improved Approximation Algorithms for Inventory Problems arXiv
  Thomas Bosman and Neil Olver
  Proceedings of the 21st Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 91–103, 2020
  schedulingapproximation
• Approximate Multi-Matroid Intersection via Iterative Refinement arXiv
  André Linhares, Neil Olver, Chaitanya Swamy and Rico Zenklusen
  Mathematical Programming, 183:397–418, 2020
  Conference version: Proceedings of the 20th Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 299–312, 2019
  approximation
• Algorithms for Flows Over Time with Scheduling Costs arXiv
  Dario Frascaria and Neil Olver
  Proceedings of the 21st Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 130–143, 2020
  flowscheduling
• Fixed-Order Scheduling on Parallel Machines
  Thomas Bosman, Dario Frascaria, Neil Olver, René Sitters and Leen Stougie
  Proceedings of the 20th Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 88–100, 2019
  scheduling
• Approximate Multi-Matroid Intersection via Iterative Refinement arXiv
  André Linhares, Neil Olver, Chaitanya Swamy and Rico Zenklusen
  Proceedings of the 20th Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 299–312, 2019
  approximation
• The Itinerant List Update Problem
  Neil Olver, Kirk Pruhs, Kevin Schewior, René Sitters and Leen Stougie
  Proceedings of the 16th Workshop on Approximation and Online Algorithms (WAOA), 2018
  scheduling
• Fast, Deterministic and Sparse Dimensionality Reduction
  Daniel Dadush, Cristóbal Guzmán and Neil Olver
  Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1330–1344, 2018
  probabilityoptimization
• Chain-Constrained Spanning Trees
  Neil Olver and Rico Zenklusen
  Mathematical Programming, 167(2):293–314, 2018
  Conference version: Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 324–335, 2013
  networksapproximation
• Exploring the Tractability of the Capped Hose Model
  Thomas Bosman and Neil Olver
  Proceedings of the 25th Annual European Symposium on Algorithms (ESA), pp. 19:1–19:12, 2017
  networks
• On the Integrality Gap of the Prize-Collecting Steiner Forest LP arXiv
  Jochen Könemann, Neil Olver, Kanstantsin Pashkovich, R. Ravi, Chaitanya Swamy and Jens Vygen
  Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), pp. 17:1–17:13, 2017
  networks
• Explosion and Linear Transit Times in Infinite Trees arXiv
  Omid Amini, Luc Devroye, Simon Griffiths and Neil Olver
  Probability Theory and Related Fields, 167(1):325–347, 2017
  probability
• Long Term Behavior of Dynamic Equilibria in Fluid Queuing Networks arXiv
  Roberto Cominetti, José Correa and Neil Olver
  Proceedings of the 19th Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 161–172, 2017
  flowgame theory
• A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization arXiv
  Neil Olver and László Végh
  Proceedings of the 49th ACM Symposium on Theory of Computing (STOC), pp. 100–111, 2017
  flowoptimization
• A Note on Hierarchical Hubbing for a Generalization of the VPN Problem arXiv
  Neil Olver
  Operations Research Letters, 44(2):191–195, 2016
  networks
• On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree
  Andreas Emil Feldmann, Jochen Könemann, Neil Olver and Laura Sanità
  Mathematical Programming, 160(1):379–406, 2016
  Conference version: Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), 2014
  networksapproximation
• Adaptive Rumour Spreading
  José Correa, Marcos Kiwi, Neil Olver and Alfredo Vera
  Proceedings of the 11th International Conference on Web and Internet Economics (WINE), pp. 272–285, 2015
  probabilitynetworks
• Decentralized Utilitarian Mechanisms for Scheduling Games arXiv
  Richard Cole, José Correa, Vasilis Gkatzelis, Vahab Mirrokni and Neil Olver
  Games and Economic Behavior, 92:306–326, 2015
  Conference version: Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pp. 539–548, 2011
  game theoryscheduling
• Pipage Rounding, Pessimistic Estimators and Matrix Concentration arXiv
  Nicholas Harvey and Neil Olver
  Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 926–945, 2014
  probabilityoptimization
• Approximability of Robust Network Design
  Neil Olver and F. Bruce Shepherd
  Mathematics of Operations Research, 39(2):561–572, 2014
  Conference version: Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1097–1105, 2010
  networksapproximation
• On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree
  Andreas Emil Feldmann, Jochen Könemann, Neil Olver and Laura Sanità
  Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), 2014
  networksapproximation
• The VPN Conjecture is True
  Navin Goyal, Neil Olver and F. Bruce Shepherd
  Journal of the ACM, 60(3), 2013
  Conference version: Proceedings of the 40th ACM Symposium on Theory of Computing (STOC), pp. 443–450, 2008
  networks
• On Explosions in Heavy-Tailed Branching Random Walks arXiv
  Omid Amini, Luc Devroye, Simon Griffiths and Neil Olver
  Annals of Probability, 41(3B):1864–1899, 2013
  probability
• Chain-Constrained Spanning Trees
  Neil Olver and Rico Zenklusen
  Proceedings of the 16th Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 324–335, 2013
  networksapproximation
• Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations arXiv
  Michel X. Goemans, Neil Olver, Thomas Rothvoß and Rico Zenklusen
  Proceedings of the 44th ACM Symposium on Theory of Computing (STOC), pp. 1161–1176, 2012
  networksapproximation
• Dynamic vs Oblivious Routing in Network Design arXiv
  Navin Goyal, Neil Olver and F. Bruce Shepherd
  Algorithmica, 61(1):161–173, 2011
  Conference version: Proceedings of the 17th Annual European Symposium on Algorithms (ESA), pp. 277–288, 2009
  networks
• Inner Product Spaces for MinSum Coordination Mechanisms arXiv
  Richard Cole, José Correa, Vasilis Gkatzelis, Vahab Mirrokni and Neil Olver
  Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pp. 539–548, 2011
  game theoryscheduling
• Approximability of Robust Network Design
  Neil Olver and F. Bruce Shepherd
  Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1097–1105, 2010
  networksapproximation
• Dynamic vs Oblivious Routing in Network Design arXiv
  Navin Goyal, Neil Olver and F. Bruce Shepherd
  Proceedings of the 17th Annual European Symposium on Algorithms (ESA), pp. 277–288, 2009
  networks
• A Priority-Based Model of Routing
  Babak Farzad, Neil Olver and Adrian Vetta
  Chicago Journal of Theoretical Computer Science, 1:1:1–1:28, 2008
  networksgame theory
• The VPN Conjecture is True
  Navin Goyal, Neil Olver and F. Bruce Shepherd
  Proceedings of the 40th ACM Symposium on Theory of Computing (STOC), pp. 443–450, 2008
  networks
• A Polynomial Time Algorithm for Finding Nash Equilibria in Planar Win-Lose Games
  Louigi Addario-Berry, Neil Olver and Adrian Vetta
  Journal of Graph Algorithms and Applications, 11(1):309–319, 2007
  game theory
• Complex Sine-Gordon-2: A New Algorithm for Multivortex Solutions on the Plane
  Neil Olver and Igor V. Barashenkov
  Theoretical and Mathematical Physics, 144(2):1223–1226, 2005