14 citations · 19 across the 11 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
cs.DS2015★ 14 cited
Tight Bounds for Approximate Carathéodory and Beyond
Vahab Mirrokni, Renato Paes Leme, Adrian Vladu +1
We give a deterministic nearly-linear time algorithm for approximating any point inside a convex polytope with a sparse convex combination of the polytope's vertices. Our result pr…
cs.GT2015★ 1 cited
Computing Walrasian Equilibria: Fast Algorithms and Structural Properties
Renato Paes Leme, Sam Chiu-wai Wong
We present the first polynomial time algorithm for computing Walrasian equilibrium in an economy with indivisible goods and \emph{general} buyer valuations having only access to an…
cs.DS2015
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization
Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong
We improve upon the running time for finding a point in a convex set given a separation oracle. In particular, given a separation oracle for a convex set co…