15 citations · 42 across the 16 of their papers we have counts for
12 papers · 1 filter
A Strongly Polynomial Algorithm for Linear Exchange Markets
Jugal Garg, László A. Végh
We present a strongly polynomial algorithm for computing an equilibrium in Arrow-Debreu exchange markets with linear utilities. Our algorithm is based on a variant of the weakly-po…
A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
Ola Svensson, Jakub Tarnawski, László A. Végh
We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem (ATSP). Our approximation guarantee is analyzed with respect to the standard LP rela…
A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization
Neil Olver, László A. Végh
We present a new strongly polynomial algorithm for generalized flow maximization that is significantly simpler and faster than the previous strongly polynomial algorithm [Végh16].…
A 7/3-Approximation for Feedback Vertex Sets in Tournaments
Matthias Mnich, Virginia Vassilevska Williams, László A. Végh
We consider the minimum-weight feedback vertex set problem in tournaments: given a tournament with non-negative vertex weights, remove a minimum-weight set of vertices that interse…
Constant Factor Approximation for ATSP with Two Edge Weights
Ola Svensson, Jakub Tarnawski, László A. Végh
We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the…
A Rational Convex Program for Linear Arrow-Debreu Markets
Nikhil R. Devanur, Jugal Garg, László A. Végh
We give a new, flow-type convex program describing equilibrium solutions to linear Arrow-Debreu markets. Whereas convex formulations were previously known [Nenakov, Primak 83; Jain…