PhD Thesis

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

Journal publications

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.
László A. Végh and András Frank.
Discrete Optimization, 5:677-684, 2008.

Conference proceedings (without journal version)

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
Constant Factor Approximation for ATSP with Two Edge Weights
Ola Svensson, Jakub Tarnawski, László A. Végh
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

Approximating minimum cost connectivity orientation and augmentation
Mohit Singh, László A. Végh.
SODA 2014
Splitting property via shadow systems
Kirstó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

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.