Végh, László A.

Number of items: 67.
None
  • Garg, Jugal, Tao, Yixin, Végh, László A. (2025). Approximating competitive equilibrium by Nash welfare. In Azar, Yossi, Panigrahi, Debmalya (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
  • 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, Jens, Byrka, Jarosław (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, 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
  • 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, Barna, Servedio, Rocco 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, Alberto, Kaibel, Volker (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, Alberto, Kaibel, Volker (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
  • Dadush, Daniel, Koh, Zhuan Khye, Natura, Bento, Végh, László A A. (2022). On circuit diameter bounds via circuit imbalances. In Aardal, Karen, Sanità, Laura (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
  • 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
  • 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.
  • 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
  • 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. (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
  • 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.
  • 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, Fedor V., Freivalds, Rūsiņš, Kwiatkowska, Marta, Peleg, David (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
  • 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.
  • 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
  • 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.
  • 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.
  • 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.
  • 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
  • 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.
    • Public
  • 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
  • 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, NK (Eds.), 42nd International Symposium On Theoretical Aspects Of Computer Science, Stacs 2025 . https://doi.org/10.4230/LIPIcs.STACS.2025.2 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, 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, Bojan, Shinkar, Igor, O�Donnell, Ryan (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
  • 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
  • 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
  • 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, Joseph (Seffi), Buchbinder, Niv (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, Joseph (Seffi), Buchbinder, Niv (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, Joseph (Seffi), Buchbinder, Niv (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, Petra, Pagh, Rasmus, Herman, Grzegorz (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
  • 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
  • Garg, Jugal, Husić, Edin, Végh, László A. (2021). Approximating Nash social welfare under rado valuations. In Khuller, Samir, Williams, Virginia Vassilevska (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, Markus, Monmege, Benjamin (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
  • 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
  • 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, Konstantin, Makarychev, Yury, Tulsiani, Madhur, Kamath, Gautam, Chuzhoy, Julia (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
  • 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
  • Loho, Georg, Végh, László A. (2020). Signed tropical convexity. In Vidick, Thomas (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, Moses, Cohen, Edith (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
  • 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
  • Dadush, Daniel, Végh, László A., Zambelli, Giacomo (2018). Geometric rescaling algorithms for submodular function minimization. In Czumaj, Artur (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
  • 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
  • Dadush, Daniel, Végh, László A., Zambelli, Giacomo (2016). Rescaled coordinate descent methods for linear programming. In Louveaux, Quentin, Skutella, Martin (Eds.), Integer Programming and Combinatorial Optimization (pp. 26-37). Springer Berlin / Heidelberg. https://doi.org/10.1007/978-3-319-33461-5_3
  • 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
  • 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
    • Restricted
  • Orlin, James B., Végh, László A. (2022). Directed shortest paths via approximate cost balancing. In Marx, Daniel (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
  • 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