Journal publications

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
Conference version: STOC 2018, Best Paper Award
Talk at Simons Institute
Article in Quanta Magazine
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
Conference version: STOC 2017
Geometric Rescaling Algorithms for Submodular Function Minimization
Daniel Dadush, László A. Végh, Giacomo Zambelli
Accepted to Mathematics of Operations Research, 2020
Conference version: SODA 2018
Rescaling Algorithms for Linear Conic Feasibility
Daniel Dadush, László A. Végh, Giacomo Zambelli
Mathematics of Operations Research, 45(2):403–795, 2020
Partly based on IPCO 2016 paper.
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
Conference version: SODA 2014
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
Conference version: IPCO 2016
A strongly polynomial algorithm for generalized flow maximization
László A. Végh
Mathematics of Operations Research, 42(1):179–211, 2017
Conference version: STOC 2014
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
Conference version: STOC 2012
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
Conference version: FOCS 2012
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
Conference version: ICALP 2013
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
Conference version: WINE 2012
Approximating minimum-cost k-node connected subgraphs via independence-free graphs
Joseph Cheriyan, László A. Végh
SIAM Journal on Computing 43(4):1342–1362, 2014
Conference version: FOCS 2013 Video
A polynomial projection-type algorithm for linear programming
László A. Végh, Giacomo Zambelli
Operations Research Letters 42:91–96, 2014
Concave generalized flows with applications to market equilibria.
László A. Végh
Mathematics of Operations Research 39(2):573–596, 2014
Conference version: FOCS 2012 Video
Augmenting undirected node-connectivity by one.
László A. Végh
SIAM J. Discrete Math. 2(25):695–718, 2011
Conference version: STOC 2010. Danny Lewin Best Student Paper Prize.
The constructive characterization of (k,l)-edge-connected digraphs.
Erika R. Kovács and László A. Végh
Combinatorica, 31(2):201–223, 2011.
Primal-dual approach for directed vertex connectivity augmentation and generalizations.
László A. Végh and András A. Benczúr
ACM Transactions on Algorithms, 4(2), 2008.
Conference version: SODA 2005
An algorithm to increase the node-connectivity of a digraph by one.
András Frank and László A. Végh
Discrete Optimization, 5:677–684, 2008.


Conference proceedings (without journal version)

Approximating Nash Social Welfare under Rado Valuations
Jugal Garg, Edin Husić, László A. Végh
Accepted to STOC 2021.
Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands
Jugal Garg, Edin Husić, László A. Végh
STACS 2021
Directed Shortest Paths via Approximate Cost Balancing
James B. Orlin, László A. Végh
SODA 2021
Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers
Daniel Dadush, Bento Natura, László A. Végh
FOCS 2020
A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
Daniel Dadush, Sophie Huiberts, Bento Natura, László A. Végh
STOC 2020
Talk at the Aussois Combinatorial Optimization Workshop
Signed tropical convexity
Georg Loho, László A. Végh
ITCS 2020
A Strongly Polynomial Algorithm for Linear Exchange Markets
Jugal Garg, László A. Végh
STOC 2019
Decomposable Submodular Function Minimization: Discrete and Continuous
Alina Ene, Huy L. Nguyen, László A. Végh
NIPS 2017
A 7/3-Approximation for Feedback Vertex Sets in Tournaments
Matthias Mnich, Virginia Vassilevska Williams, László A. Végh
ESA 2016
Rescaled coordinate descent methods for Linear Programming
Daniel Dadush, László A. Végh, Giacomo Zambelli
IPCO 2016
To Save Or Not To Save: The Fisher Game
Ruta Mehta, Nithum Thain, László A. Végh, and Adrian Vetta
WINE 2014
Splitting property via shadow systems
Kristóf Bérczi, Péter Csikvári, Erika R. Kovács, and László A. Végh
Japanese Hungarian Symposium on Discrete Mathematics and its Applications, 2013
Restricted b-matchings in degree-bounded graphs.
Kristóf Bérczi and László A. Végh
IPCO 2010, pages 43-56.
Nonadaptive selfish routing with online demands.
Tobias Harks and László A. Végh
CAAN 2007, pages 27-45.


Invited survey

Constructive characterization theorems in combinatorial optimization.
Erika R. Kovács and László A. Végh
RIMS Kôkyûroku Bessatsu, B23:147-169, 2010


PhD Thesis

Connectivity Augmentation Algorithms
Eötvös University, June 2010.
Advisor: András Frank.


Other papers

Algorithms for multiplayer multicommodity flow problems
A. Bernáth, T. Király, E. R. Kovács, G. Mádi-Nagy, Gy. Pap, J. Pap, J. Szabó, L. A. Végh
Central European Journal of Operations Research, 21:699-712.
Worst case bin packing for OTN electrical layer networks dimensioning
T. Király, A. Bernáth, L. A. Végh, L. Bajzik, E. R. Kovács, K. Bérczi, A. Jüttner, T. Jordán
ICTON 2011.
ILP based diverse path routing with node inclusion
Zs. Lakatos, L. Bajzik, T. Kárász, K. Bérczi, E. R. Kovács, L. A. Végh
ICUMT 2011.



Technical Reports

The list of my EGRES Technical Reports can be found here.