Y. Ye

activity

20072009

most citedFast and Near-Optimal Matrix Completion via Randomized Basis Pursuit

11 citations · 21 across the 7 of their papers we have counts for

collaborators

Showing cs.DSShow all

2 papers · 1 filter

cs.DS2008★ 4 cited

Stochastic Combinatorial Optimization under Probabilistic Constraints

Shipra Agrawal, Amin Saberi, Yinyu Ye

In this paper, we present approximation algorithms for combinatorial optimization problems under probabilistic constraints. Specifically, we focus on stochastic variants of two imp…

cs.DS2007★ 1 cited

A polynomial time $\frac{3}{2}$ -approximation algorithm for the vertex cover problem on a class of graphs

Qiaoming Han, Abraham P. Punnen, Yinyu Ye

We develop a polynomial time 3/2-approximation algorithm to solve the vertex cover problem on a class of graphs satisfying a property called ``active edge hypothesis''. The algorit…

Stochastic Combinatorial Optimization under Probabilistic Constraints

A polynomial time 23​ -approximation algorithm for the vertex cover problem on a class of graphs

A polynomial time $\frac{3}{2}$ -approximation algorithm for the vertex cover problem on a class of graphs