1.6k citations · 3.6k across the 48 of their papers we have counts for
Showing 2010Show all
2 papers · 1 filter
cs.DS2010★ 13 cited
Combinatorial Approximation Algorithms for MaxCut using Random Walks
Satyen Kale, C. Seshadhri
We give the first combinatorial approximation algorithm for Maxcut that beats the trivial 0.5 factor by a constant. The main partitioning procedure is very intuitive, natural, and…
math.OC2010★ 17 cited
An optimal algorithm for stochastic strongly-convex optimization
Elad Hazan, Satyen Kale
We consider stochastic convex optimization with a strongly convex (but not necessarily smooth) objective. We give an algorithm which performs only gradient updates with optimal rat…