15 citations · 42 across the 16 of their papers we have counts for
5 papers · 1 filter
On finding exact solutions of linear programs in the oracle model
Daniel Dadush, László A. Végh, Giacomo Zambelli
We consider linear programming in the oracle model: , where the polyhedron is given by a separation oracle. We…
Signed tropical convexity
Georg Loho, László A. Végh
We establish a new notion of tropical convexity for signed tropical numbers. We provide several equivalent descriptions involving balance relations and intersections of open halfsp…
Geometric Rescaling Algorithms for Submodular Function Minimization
Daniel Dadush, László A. Végh, Giacomo Zambelli
We present a new class of polynomial-time algorithms for submodular function minimization (SFM), as well as a unified framework to obtain strongly polynomial SFM algorithms. Our al…
Rescaling Algorithms for Linear Conic Feasibility
Daniel Dadush, László A. Végh, Giacomo Zambelli
We propose simple polynomial-time algorithms for two linear conic feasibility problems. For a matrix , the kernel problem requires a positive vector in…
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…