Journal publications

On complete classes of valuated matroids
Edin Husić, Georg Loho, Ben Smith, László A. Végh
TheoretiCS (accepted), 2024
Conference version: SODA 2022
On the Correlation Gap of Matroids
Edin Husić, Zhuan Khye Koh, Georg Loho, László A. Végh
Mathematical Programming (accepted), 2024
Conference version: IPCO 2023
On Circuit Diameter Bounds via Circuit Imbalances
Daniel Dadush, Zhuan Khye Koh, Bento Natura, László A. Végh
Mathematical Programming (accepted), 2024
Conference version: IPCO 2022
An Update-and-Stabilize Framework for the Minimum-Norm-Point Problem
Satoru Fujishige, Tomonari Kitahara, László A. Végh
Mathematical Programming (accepted), 2024
Conference version: IPCO 2023
Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands
Jugal Garg, Edin Husić, László A. Végh
ACM TEAC, 11(3–4):7, 2023
Conference version: STACS 2021
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
Mathematical Programming, 204:135–206, 2024
Conference version: STOC 2020
Talk at the Aussois Combinatorial Optimization Workshop
An Accelerated Newton-Dinkelbach Method and its Application to Two Variables Per Inequality Systems
Daniel Dadush, Zhuan Khye Koh, Bento Natura, László A. Végh
Mathematics of Operations Research, 48(4):1934–1958, 2022
Conference version: ESA 2021
Directed Shortest Paths via Approximate Cost Balancing
James B. Orlin, László A. Végh
Journal of the ACM, 70(1):3, 2022
Conference version: SODA 2021
Circuit imbalance measures and linear programming
Farbod Ekbatani, Bento Natura, László A. Végh
Surveys in Combinatorics 2022. London Mathematical Society Lecture Note Series. pp. 64–114, 2022
A Strongly Polynomial Algorithm for Linear Exchange Markets
Jugal Garg, László A. Végh
Operations Research, 71(2):487–505, 2023
Conference version: STOC 2019
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
Mathematics of Operations Research 46(3):1081–1108, 2021
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)

A strongly polynomial algorithm for linear programs with at most two non-zero entries per row or column
Daniel Dadush, Zhuan Khye Koh, Bento Natura, Neil Olver, and László A. Végh
STOC 2024
A First Order Method for Linear Programming Parameterized by Circuit Imbalance
Richard Cole, Christoph Hertrich, Yixin Tao, László A. Végh
IPCO 2024
Faster Ascending Auctions via Polymatroid Sum
Katharina Eickhoff, Britta Peis, Niklas Rieken, Laura Vargas Koch, László A. Végh
WINE 2023

Mode Connectivity in Auction Design
Christoph Hertrich, Yixin Tao, László A. Végh
NeurIPS 2023

Approximating Nash Social Welfare by Matching and Local Search
Jugal Garg, Edin Husić, Wenzheng Li, László A. Végh, Jan Vondrák
STOC 2023
Tractable Fragments of the Maximum Nash Welfare Problem
Jugal Garg, Edin Husić, Aniket Murhekar, László A. Végh
WINE 2022
Interior point methods are not worse than Simplex
Xavier Allamigeon, Daniel Dadush, Georg Loho, Bento Natura, László A. Végh
FOCS 2022
On finding exact solutions of linear programs in the oracle model
Daniel Dadush, Giacomo Zambelli, László A. Végh
SODA 2022

Approximating Equilibrium under Constrained Piecewise Linear Concave Utilities with Applications to Matching Markets
Jugal Garg, Yixin Tao, László A. Végh
SODA 2022
Approximating Nash Social Welfare under Rado Valuations
Jugal Garg, Edin Husić, László A. Végh
STOC 2021.
Summary in Sigecom Exchanges
Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers
Daniel Dadush, Bento Natura, László A. Végh
FOCS 2020
Signed tropical convexity
Georg Loho, László A. Végh
ITCS 2020
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 surveys

Circuit imbalance measures and linear programming
Farbod Ekbatani, Bento Natura, László A. Végh
Surveys in Combinatorics 2022. London Mathematical Society Lecture Note Series. pp. 64–114, 2022
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.