Végh, László A.

Number of items: 67.
Article
  • Allamigeon, Xavier, Dadush, Daniel, Loho, Georg, Natura, Bento, Végh, László A. (2025). Interior point methods are not worse than simplex. SIAM Journal on Computing, 54(5), FOCS22-178 - FOCS22-264. https://doi.org/10.1137/23m1554588 picture_as_pdf
  • Eickhoff, Katharina, Neuwohner, Meike, Peis, Britta, Rieken, Niklas, Vargas Koch, Laura, Végh, Lázló A. (2025). Faster dynamic auctions via polymatroid sum. ACM Transactions on Economics and Computation, 13(3), 1 - 47. https://doi.org/10.1145/3729429 picture_as_pdf
  • Cole, Richard, Hertrich, Christoph, Tao, Yixin, Vegh, Laszlo A. (2025). A first order method for linear programming parameterized by circuit imbalance. Mathematical Programming, https://doi.org/10.1007/s10107-025-02264-7 picture_as_pdf
  • Koh, Zhuan Khye, Husic, Edin, Loho, Georg, Végh, László A. (2025). On the correlation gap of matroids. Mathematical Programming, 210(1-2), 407 - 456. https://doi.org/10.1007/s10107-024-02116-w picture_as_pdf
  • Fujishige, Satoru, Kitahara, Tomonari, Végh, László A. (2025). An update-and-stabilize framework for the minimum-norm-point problem. Mathematical Programming, 210(1), 281 - 311. https://doi.org/10.1007/s10107-024-02077-0 picture_as_pdf
  • Koh, Zhuan Khye, Natura, Bento, Végh, László A. (2024). On circuit diameter bounds via circuit imbalances. Mathematical Programming, 206(1-2), 631 - 662. https://doi.org/10.1007/s10107-024-02107-x picture_as_pdf
  • Dadush, Daniel, Huiberts, Sophie, Natura, Bento, Végh, László A. (2024). A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix. Mathematical Programming, 204(1-2), 135 – 206. https://doi.org/10.1007/s10107-023-01956-2 picture_as_pdf
  • Garg, Jugal, Husić, Edin, Végh, László A. (2023). An auction algorithm for market equilibrium with weak gross substitute demands. ACM Transactions on Economics and Computation, 11(3-4), 1 - 24. https://doi.org/10.1145/3624558
  • Dadush, Daniel, Koh, Zhuan Khye, Natura, Bento, Végh, László A. (2023). An accelerated Newton–Dinkelbach method and its application to two variables per inequality systems. Mathematics of Operations Research, 48(4), 1934 - 1958. https://doi.org/10.1287/moor.2022.1326 picture_as_pdf
  • Garg, Jugal, Végh, László A. (2023). A strongly polynomial algorithm for linear exchange markets. Operations Research, 71(2), 487 - 505. https://doi.org/10.1287/opre.2021.2258 picture_as_pdf
  • Orlin, James B., Végh, László A. (2023). Directed shortest paths via approximate cost balancing. Journal of the ACM, 70(1). https://doi.org/10.1145/3565019 picture_as_pdf
  • Dadush, Daniel, Végh, László A., Zambelli, Giacomo (2021). Geometric rescaling algorithms for submodular function minimization. Mathematics of Operations Research, 46(3), 1081 - 1108. https://doi.org/10.1287/moor.2020.1064 picture_as_pdf
  • Svensson, Ola, Tarnawski, Jakub, Végh, László A. (2020). A constant-factor approximation algorithm for the asymmetric traveling salesman problem. Journal of the ACM, 67(6). https://doi.org/10.1145/3424306 picture_as_pdf
  • Olver, Neil, Végh, László A. (2020). A simpler and faster strongly polynomial algorithm for generalized flow maximization. Journal of the ACM, 67(2). https://doi.org/10.1145/3383454 picture_as_pdf
  • Dadush, Daniel, Végh, László A., Zambelli, Giacomo (2020). Rescaling algorithms for linear conic feasibility. Mathematics of Operations Research, 45(2), 732 - 754. https://doi.org/10.1287/moor.2019.1011 picture_as_pdf
  • Svensson, Ola, Tarnawski, Jakub, Végh, László A. (2018). Constant factor approximation for ATSP with two edge weights. Mathematical Programming, 172(1-2), 371-397. https://doi.org/10.1007/s10107-017-1195-7
  • Singh, Mohit, Végh, László A. (2018). Approximating minimum cost connectivity orientation and augmentation. SIAM Journal on Computing, 47(1), 270-293. https://doi.org/10.1137/15100583X
  • Devanur, Nikhil R., Garg, Jugal, Végh, László A. (2016). A rational convex program for linear Arrow-Debreu markets. ACM Transactions on Economics and Computation, 5(1), p. 6. https://doi.org/10.1145/2930658
  • Végh, László A. (2016). A strongly polynomial algorithm for generalized flow maximization. Mathematics of Operations Research, 42(1), 179-211. https://doi.org/10.1287/moor.2016.0800
  • Végh, László A. (2016). A strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives. SIAM Journal on Computing, 45(5), 1729-1761. https://doi.org/10.1137/140978296
  • Chandrasekaran, Karthekeyan, Végh, László A., Vempala, Santosh S. (2016). The cutting plane method is polynomial for perfect matchings. Mathematics of Operations Research, 41(1), 23-48. https://doi.org/10.1287/moor.2015.0714
  • Mnich, Matthias, Williams, Virginia Vassilevska, Végh, László A. (2016). A 7/3-approximation for feedback vertex sets in tournaments. Leibniz International Proceedings in Informatics, (57), 67:1-67:14. https://doi.org/10.4230/LIPIcs.ESA.2016.67
  • Marx, Dániel, Végh, László A. (2015). Fixed-parameter algorithms for minimum-cost edge-connectivity augmentation. ACM Transactions on Algorithms, 11(4), p. 27. https://doi.org/10.1145/2700210
  • Végh, László A., von Stengel, Bernhard (2015). Oriented Euler complexes and signed perfect matchings. Mathematical Programming, 150(1), 153-178. https://doi.org/10.1007/s10107-014-0770-4
  • Piliouras, Georgios, Valla, Tomáš, Végh, László A. (2014). LP-based covering games with low price of anarchy. Theory of Computing Systems, 57(1), 238-260. https://doi.org/10.1007/s00224-014-9587-z
  • Végh, László A. (2014). Concave generalized flows with applications to market equilibria. Mathematics of Operations Research, 39(2), 573-596. https://doi.org/10.1287/moor.2013.0623
  • Végh, László A., Zambelli, Giacomo (2014). A polynomial projection-type algorithm for linear programming. Operations Research Letters, 42(1), 91-96. https://doi.org/10.1016/j.orl.2013.12.007
  • Cheriyan, Joseph, Végh, László A. (2014). Approximating minimum-cost -node connected subgraphs via independence-free graphs. SIAM Journal on Computing, 43(4), 1342-1362. https://doi.org/10.1137/120902847
  • Végh, László A. (2011). Augmenting undirected node-connectivity by one. SIAM Journal on Discrete Mathematics, 25(2), 695-718. https://doi.org/10.1137/100787507
  • Kovács, Erika Renáta, Végh, László (2011). The constructive characterization of (k,l)-edge-connected digraphs. Combinatorica, 31(2), 201-223. https://doi.org/10.1007/s00493-011-2570-2
  • Kovács, Erika Renáta, Vegh, László (2010). Constructive characterization theorems in combinatorial optimization. Rims Kôkyûroku Bessatsu, B23, 147-169.
  • Frank, András, Végh, László A. (2008). An algorithm to increase the node-connectivity of a digraph by one. Discrete Optimization, 5(4), 677-684. https://doi.org/10.1016/j.disopt.2008.03.002
  • Végh, László A., Benczúr, András A. (2008). Primal-dual approach for directed vertex connectivity augmentation and generalizations. ACM Transactions on Algorithms, 4(2), 20:1-20:21. https://doi.org/10.1145/1361192.1361197
    • Chapter
  • Dadush, Daniel, Koh, Zhuan Khye, Natura, Bento, Olver, Neil, Vegh, Laszlo A. (2025). A strongly polynomial algorithm for linear programs with at most two non-zero entries per row or column. In Beyersdorff, O., Pilipczuk, M., Pimentel, E. & Thang, N. (Eds.), 42nd International Symposium On Theoretical Aspects Of Computer Science, Stacs 2025 . https://doi.org/10.4230/LIPIcs.STACS.2025.2 picture_as_pdf
  • Garg, Jugal, Tao, Yixin, Végh, László A. (2025). Approximating competitive equilibrium by Nash welfare. In Azar, Y. & Panigrahi, D. (Eds.), Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 2538 - 2559). Society for Industrial and Applied Mathematics Publications. https://doi.org/10.1137/1.9781611978322.83
  • Dadush, Daniel, Koh, Zhuan Khye, Natura, Bento, Olver, Neil, Végh, László A. (2024). A strongly polynomial algorithm for linear programs with at most two nonzero entries per row or column. In Mohar, B., Shinkar, I. & O�Donnell, R. (Eds.), STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC ’24), June 24–28 (pp. 1561 – 1572). ACM Press. https://doi.org/10.1145/3618260.3649764 picture_as_pdf
  • Cole, Richard, Hertrich, Christoph, Tao, Yixin, Végh, László A. (2024). A first order method for linear programming parameterized by circuit imbalance. In Vygen, J. & Byrka, J. (Eds.), Integer Programming and Combinatorial Optimization - 25th International Conference, IPCO 2024, Proceedings (pp. 57 - 70). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-59835-7_5
  • Garg, Jugal, Husić, Edin, Li, Wenzheng, Végh, László A., Vondrák, Jan (2023). Approximating Nash social welfare by matching and local search. In Saha, B. & Servedio, R. A. (Eds.), STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing (pp. 1298-1310). Association for Computing Machinery. https://doi.org/10.1145/3564246.3585255
  • Husić, Edin, Koh, Zhuan Khye, Loho, Georg, Végh, László A. (2023). On the correlation gap of matroids. In Del Pia, A. & Kaibel, V. (Eds.), Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Proceedings (pp. 203-216). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-32726-1_15
  • Fujishige, Satoru, Kitahara, Tomonari, Végh, László A. (2023). An update-and-stabilize framework for the minimum-norm-point problem. In Del Pia, A. & Kaibel, V. (Eds.), Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Proceedings (pp. 142-156). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-32726-1_11
  • Orlin, James B., Végh, László A. (2022). Directed shortest paths via approximate cost balancing. In Marx, D. (Ed.), ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 (pp. 235 - 254). Association for Computing Machinery. https://doi.org/10.1137/1.9781611976465.16 picture_as_pdf
  • Dadush, Daniel, Koh, Zhuan Khye, Natura, Bento, Végh, László A A. (2022). On circuit diameter bounds via circuit imbalances. In Aardal, K. & Sanità, L. (Eds.), Integer Programming and Combinatorial Optimization - 23rd International Conference, IPCO 2022, Proceedings (pp. 140 - 153). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-06901-7_11
  • Garg, Jugal, Tao, Yixin, Végh, László A. (2022). Approximating equilibrium under constrained piecewise linear concave utilities with applications to matching markets. In Naor, print. & Buchbinder, N. (Eds.), Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 2269 - 2284). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977073.91 picture_as_pdf
  • Husić, Edin, Loho, Georg, Smith, Ben, Végh, László A. (2022). On complete classes of valuated matroids. In Naor, print. & Buchbinder, N. (Eds.), Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 945 - 962). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977073.41 picture_as_pdf
  • Dadush, Daniel, Végh, László A., Zambelli, Giacomo (2022). On finding exact solutions of linear programs in the oracle model. In Naor, print. & Buchbinder, N. (Eds.), Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 2700 - 2722). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977073.106 picture_as_pdf
  • Dadush, Daniel, Koh, Zhuan Khye, Natura, Bento, Végh, László A. (2021). An accelerated Newton-dinkelbach method and its application to two variables per inequality systems. In Mutzel, P., Pagh, R. & Herman, G. (Eds.), 29th Annual European Symposium on Algorithms, ESA 2021 . Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ESA.2021.36 picture_as_pdf
  • Garg, Jugal, Husić, Edin, Végh, László A. (2021). Approximating Nash social welfare under rado valuations. In Khuller, S. & Williams, V. V. (Eds.), STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (pp. 1412 - 1425). Association for Computing Machinery. https://doi.org/10.1145/3406325.3451031 picture_as_pdf
  • Garg, Jugal, Husić, Edin, Végh, László A. (2021). Auction algorithms for market equilibrium with weak gross substitute demands and their applications. In Blaser, M. & Monmege, B. (Eds.), 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021 . Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.STACS.2021.33 picture_as_pdf
  • Dadush, Daniel, Natura, Bento, Végh, László A. (2020). Revisiting Tardos's framework for linear programming: faster exact solutions using approximate solvers. In Proceedings of The 61st Annual Symposium on Foundations of Computer Science (FOCS 2020), November 16-19 (pp. 931-942). IEEE Computer Society. picture_as_pdf
  • Dadush, Daniel, Huiberts, Sophie, Natura, Bento, Végh, László A. (2020). A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix. In Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G. & Chuzhoy, J. (Eds.), STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (pp. 761-774). Association for Computing Machinery. https://doi.org/10.1145/3357713.3384326 picture_as_pdf
  • Loho, Georg, Végh, László A. (2020). Signed tropical convexity. In Vidick, T. (Ed.), 11th Innovations in Theoretical Computer Science Conference, ITCS 2020 . Schloss Dagstuhl, Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITCS.2020.24 picture_as_pdf
  • Garg, Jugal, Végh, László A. (2019). A strongly polynomial algorithm for linear exchange markets. In Charikar, M. & Cohen, E. (Eds.), STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (pp. 54-65). https://doi.org/10.1145/3313276.3316340 picture_as_pdf
  • Dadush, Daniel, Végh, László A., Zambelli, Giacomo (2018). Geometric rescaling algorithms for submodular function minimization. In Czumaj, A. (Ed.), Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 832-848). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611975031.54 picture_as_pdf
  • Svensson, Ola, Tarnawski, Jakub, Végh, László A. (2018). A constant-factor approximation algorithm for the asymmetric traveling salesman problem. In Proceedings of 50th Annual ACM SIGACT Symposium on the Theory of Computing (STOC’18) (pp. 204-213). Association for Computing Machinery. https://doi.org/10.1145/3188745.3188824 picture_as_pdf
  • Ene, Alina, Nguyen, Huy, Végh, László A. (2017). Decomposable submodular function minimization: discrete and continuous. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S. & Garnett, R. (Eds.), Advances in Neural Information Processing Systems 30 (NIPS 2017) pre-proceedings . Neural Information Processing Systems Foundation.
  • Olver, Neil, Végh, László A. (2017). A simpler and faster strongly polynomial algorithm for generalized flow maximization. In STOC: ACM Symposium on Theory of Computing (pp. 100 - 111). ACM Press. https://doi.org/10.1145/3055399.3055439
  • Dadush, Daniel, Végh, László A., Zambelli, Giacomo (2016). Rescaled coordinate descent methods for linear programming. In Louveaux, Q. & Skutella, M. (Eds.), Integer Programming and Combinatorial Optimization (pp. 26-37). Springer Berlin / Heidelberg. https://doi.org/10.1007/978-3-319-33461-5_3
  • Végh, László A. (2013). Concave generalized flows with applications to market equilibria. In Proceedings of the IEEE 53rd Symposium on Foundations of Computer Science (Focs) 2012 (pp. 150-159). IEEE Computer Society.
  • Marx, Dániel, Végh, László A. (2013). Fixed-parameter algorithms for minimum cost edge-connectivity augmentation. In Fomin, F. V., Freivalds, R., Kwiatkowska, M. & Peleg, D. (Eds.), Automata, Languages, and Programming: 40th International Colloquium, Icalp 2013, Riga, Latvia, July 8-12, 2013 (pp. 721-732). Springer Berlin / Heidelberg. https://doi.org/10.1007/978-3-642-39206-1_61
  • Chandrasekaran, Karthekeyan, Végh, László A., Vempala, Santosh (2013). The cutting plane method is polynomial for perfect matchings. In Proceedings of the IEEE 53rd Symposium on Foundations of Computer Science (Focs) 2012 (pp. 571-580). IEEE Computer Society. https://doi.org/10.1109/FOCS.2012.35
    • Conference or Workshop Item
  • Olver, Neil, Végh, László A. (2017-06-19 - 2017-06-23) A simpler and faster strongly polynomial algorithm for generalized flow maximization [Paper]. STOC 2017 Theory Fest: 49th Annual ACM Symposium on the Theory of Computing, Hyatt Regency, Montreal, Montreal, Canada, CAN.
  • Singh, Mohit, Végh, László A. (2014-01-05 - 2014-01-07) Approximating minimum cost connectivity orientation and augmentation [Paper]. SODA 2014 - ACM-SIAM Symposium on Discrete Algorithms, Oregon, United States, USA.
  • Cheriyan, Joseph, Végh, László A. (2013-10-27 - 2013-10-29) Approximating minimum-cost k-node connected subgraphs via independence-free graphs [Paper]. FOCS 2013 - 54th Annual Symposium on Foundations of Computer Science, Berkeley CA, United States, USA.
  • Bérczi, Kristóf, Csikvári, Péter, Kovács, Erika Renáta, Végh, László A. (2013-06-04 - 2013-06-07) Splitting property via shadow systems [Paper]. 8th Japanese Hungarian Symposium on Discrete Mathematics and its Applications, Veszprem, Hungary, HUN.
  • Piliouras, Georgios, Valla, Tomas, Végh, László A. (2012-12-01) LP-based Covering Games with Low Price of Anarchy [Paper]. WINE 2012 - Workshop on Internet & Network Economics, Liverpool, United Kingdom, GBR.
  • Bérczi, Kristóf, Végh, László A. (2010-06-09 - 2010-06-11) Restricted b-matchings in degree-bounded graphs [Paper]. The 14th Conference on Integer Programming & Combinatorial Optimization (IPCO XIV), Lausanne, Switzerland, CHE.
  • Harks, Tobias, Végh, László A. (2007-08-14) Nonadaptive selfish routing with online demands [Paper]. Fourth Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN), Halifax, Canada, CAN.