15 citations · 42 across the 16 of their papers we have counts for
5 papers · 1 filter
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…
A strongly polynomial algorithm for generalized flow maximization
László A. Végh
A strongly polynomial algorithm is given for the generalized flow maximization problem. It uses a new variant of the scaling technique, called continuous scaling. The main measure…
A polynomial projection-type algorithm for linear programming
László A. Végh, Giacomo Zambelli
We propose a simple O([n^5/\log n]L) algorithm for linear programming feasibility, that can be considered as a polynomial-time implementation of the relaxation method. Our work dra…
Approximating Minimum Cost Connectivity Orientation and Augmentation
Mohit Singh, László A. Végh
We investigate problems addressing combined connectivity augmentation and orientations settings. We give a polynomial-time 6-approximation algorithm for finding a minimum cost subg…
Fixed-parameter algorithms for minimum cost edge-connectivity augmentation
Dániel Marx, László A. Végh
We consider connectivity-augmentation problems in a setting where each potential new edge has a nonnegative cost associated with it, and the task is to achieve a certain connectivi…