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 |
JACM version
STOC version arXiv:1708.04215
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
|
JACM version
STOC version
arXiv:1611.01778
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
PDF
|
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
|
STOC version
arXiv:1307.6809
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
PDF
|
|
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
|
PDF
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
|
PDF
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
PDF
|
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
PDF
|
|
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.
PDF
|
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
PDF
|
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.
PDF
|
|
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.
PDF
|
|
|
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. |