László Végh

I am broadly interested in fundamental questions in algorithms and optimisation: exact and approximation algorithms for problems related to network design, flows, matchings, and equilibrium computation, with a particular focus on strongly polynomial computability.

I completed my PhD in mathematics at the Eötvös University in Budapest in 2010, under the supervision of András Frank, working in the Egerváry Research Group on Combinatorial Optimization. In 2011-12, I was a postdoctoral fellow at the Georgia Institute of Technology, in the School of Computer Science. I joined the Operations Research Group at LSE in 2012. I am also a DSI Affiliate with LSE's Data Science Institute.

Expertise Details

• Algorithms and optimisation; algorithms for problems related to network design; and equilibrium computation; particularly on strongly polynomial computability

Awards

• Danny Lewin Best Student Paper Award, Symposium on Theory of Computing (2010)
  

Research Summary

Dr Végh is interested in fundamental questions in combinatorial optimisation related to connectivity, flows, matchings and matroids, and also applications to areas such as mathematical economics, algorithmic game theory and network design.

Languages

• English, Hungarian

Journal publications

• A Strongly Polynomial Algorithm for Linear Exchange Markets
  Jugal Garg, László A. Végh
  Accepted to Operations Research, 2021

• A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
  Ola Svensson, Jakub Tarnawski, László A. Végh
  Journal of the ACM, 67(6):37, 2020

• A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization
  Neil Olver, László A. Végh
  Journal of the ACM, 67(2):10, 2020

• Geometric Rescaling Algorithms for Submodular Function Minimization
  Daniel Dadush, László A. Végh, Giacomo Zambelli
  Accepted to Mathematics of Operations Research, 2020

• Rescaling Algorithms for Linear Conic Feasibility
  Daniel Dadush, László A. Végh, Giacomo Zambelli
  Mathematics of Operations Research, 45(2):403–795, 2020

• On Submodular Search and Machine Scheduling
  Robbert Fokkink, Thomas Lidbetter, László A. Végh
  Mathematics of Operations Research, 44(4):1431–1449, 2019

• Approximating minimum cost connectivity orientation and augmentation
  Mohit Singh, László A. Végh
  SIAM Journal on Computing, 47(1):270–293, 2018

• Constant Factor Approximation for ATSP with Two Edge Weights
  Ola Svensson, Jakub Tarnawski, László A. Végh
  Mathematical Programming Ser. B , 172:371–397, 2017

• A strongly polynomial algorithm for generalized flow maximization
  László A. Végh
  Mathematics of Operations Research, 42(1):179–211, 2017

• A strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives.
  László A. Végh
  SIAM Journal on Computing, 45(5):1729–1761, 2016

• A Rational Convex Program for Linear Arrow-Debreu Markets
  Nikhil R. Devanur, Jugal Garg, László A. Végh
  ACM Transactions on Economics and Computation 5(1):6, 2016

• The cutting plane method is polynomial for perfect matchings
  Karthekeyan Chandrasekaran, László A. Végh, and Santosh S. Vempala
  Mathematics of Operations Research, 41(1):23–48, 2016

• Fixed-parameter algorithms for minimum cost edge-connectivity augmentation
  Dániel Marx, László A. Végh
  ACM Transactions on Algorithms, 11(4):27, 2015

• Oriented Euler complexes and signed perfect matchings
  László A. Végh, Bernhard von Stengel
  Mathematical Programming, Ser. B 150:153–178, 2015

• LP-based covering games with low price of anarchy
  Georgios Piliouras, Tomas Valla and László A. Végh
  Theory of Computing Systems 57(1):238–260, 2015