Journal publications
|
Interior point methods are not worse than Simplex
Xavier Allamigeon, Daniel Dadush, Georg Loho, Bento Natura, László A. Végh SIAM Journal on Computing, (forthcomig), 2025 FOCS 2022 special issue |
arXiv:2206.08810 | |
|
Mode Connectivity in Auction Design
Christoph Hertrich, Yixin Tao, László A. Végh Mathematics of Operations Research, Articles in Advance, 2025 Conference version: NeurIPS 2023 |
NeurIPS version
arXiv:2305.11005 |
|
|
On the Correlation Gap of Matroids
Edin Husić, Zhuan Khye Koh, Georg Loho, László A. Végh Mathematical Programming, Series B, 210:407–456, 2025 Conference version: IPCO 2023 |
arXiv:2209.09896 | |
|
An Update-and-Stabilize Framework for the Minimum-Norm-Point Problem
Satoru Fujishige, Tomonari Kitahara, László A. Végh Mathematical Programming, Series B, 210:281–311, 2025 Conference version: IPCO 2023 |
arXiv:2211.02560 | |
|
On Circuit Diameter Bounds via Circuit Imbalances
Daniel Dadush, Zhuan Khye Koh, Bento Natura, László A. Végh Mathematical Programming, Series B, 206:631–662 , 2024 Conference version: IPCO 2022 |
arXiv:2111.07913 | |
|
On complete classes of valuated matroids
Edin Husić, Georg Loho, Ben Smith, László A. Végh TheoretiCS, 3:24, 2024 Conference version: SODA 2022 |
SODA version |
|
|
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 |
STACS version
arXiv:1908:07948 | |
|
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 |
STOC version
arXiv:1912.06252 | |
|
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 |
ESA version
arXiv:2004.08634 | |
|
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 |
SODA version
arXiv:2007.07975 | |
|
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 |
arXiv:2108:03616 | |
|
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 |
STOC version
arXiv:1809.06266 | |
|
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 |
SODA version
arXiv:1707.05065 | |
|
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. |
arXiv:1611.06427 | |
|
On Submodular Search and Machine Scheduling
Robbert Fokkink, Thomas Lidbetter, László A. Végh Mathematics of Operations Research, 44(4):1431–1449, 2019 |
arXiv:1607.07598 | |
|
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 |
arXiv:1511.07038 | |
|
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 |
summary
| |
|
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 | arXiv:1207:5831 | |
|
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 |
arXiv:1210:4694 | |
|
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 |
arXiv:1203.0050 | |
|
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 | arXiv:1307.4334 | |
|
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. |
PDF
| |
|
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)
|
An O(log n)-Approximation Algorithm for (p,q)-Flexible Graph Connectivity via Independent Rounding
Sharat Ibrahimpur and László A. Végh Accepted to IPCO 2025 |
arXiv:2501.12549
| |
|
Approximating Competitive Equilibrium by Nash Welfare
Jugal Garg, Yixin Tao, László A. Végh SODA 2025 |
SODA version
arXiv:2402.09994 | |
|
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 |
STOC version
| |
|
A First Order Method for Linear Programming Parameterized by Circuit Imbalance
Richard Cole, Christoph Hertrich, Yixin Tao, László A. Végh IPCO 2024 |
arXiv:2311.01959 | |
|
Faster Ascending Auctions via Polymatroid Sum
Katharina Eickhoff, Britta Peis, Niklas Rieken, Laura Vargas Koch, László A. Végh WINE 2023 |
arXiv:2310.08454 | |
|
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 |
arXiv:2211.03883 | |
|
Tractable Fragments of the Maximum Nash Welfare Problem
Jugal Garg, Edin Husić, Aniket Murhekar, László A. Végh WINE 2022 |
arXiv:2112.10199 | |
|
On finding exact solutions of linear programs in the oracle model
Daniel Dadush, Giacomo Zambelli, László A. Végh SODA 2022
|
SODA version
|
|
|
Approximating Equilibrium under Constrained Piecewise Linear Concave Utilities with Applications to Matching Markets
Jugal Garg, Yixin Tao, László A. Végh SODA 2022 |
SODA version arXiv:2107:05700 |
|
|
Approximating Nash Social Welfare under Rado Valuations
Jugal Garg, Edin Husić, László A. Végh STOC 2021. Summary in Sigecom Exchanges |
STOC version
arXiv:2009.14793 | |
|
Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers
Daniel Dadush, Bento Natura, László A. Végh FOCS 2020 |
FOCS version
arXiv:2009.04942 | |
|
Signed tropical convexity
Georg Loho, László A. Végh ITCS 2020 | ITCS version
arXiv:1906:06686 | |
|
Decomposable Submodular Function Minimization: Discrete and Continuous
Alina Ene, Huy L. Nguyen, László A. Végh NIPS 2017 |
NIPS version
arXiv:1703.01830 | |
|
A 7/3-Approximation for Feedback Vertex Sets in Tournaments
Matthias Mnich, Virginia Vassilevska Williams, László A. Végh ESA 2016 |
ESA version
arXiv:1511.01137 | |
|
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 |
EGRES Technical Report TR-2013-02 | |
|
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 |
arXiv:2108:03616 | |
|
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. |
PDF
Summary |
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. |