12 citations · 27 across the 12 of their papers we have counts for
Showing 2012Show all
2 papers · 1 filter
cs.DS2012
Faster SDP hierarchy solvers for local rounding algorithms
Venkatesan Guruswami, Ali Kemal Sinop
Convex relaxations based on different hierarchies of linear/semi-definite programs have been used recently to devise approximation algorithms for various optimization problems. The…
cs.CC2012★ 4 cited
Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems
Venkatesan Guruswami, Ali Kemal Sinop, Yuan Zhou
Partitioning the vertices of a graph into two roughly equal parts while minimizing the number of edges crossing the cut is a fundamental problem (called Balanced Separator) that ar…