Showing cs.DSShow all
2 papers · 1 filter
cs.DS2011
Rounding Semidefinite Programming Hierarchies via Global Correlation
Boaz Barak, Prasad Raghavendra, David Steurer
We show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum…
cs.DS2006
Tight Bounds for the Min-Max Boundary Decomposition Cost of Weighted Graphs
David Steurer
Many load balancing problems that arise in scientific computing applications ask to partition a graph with weights on the vertices and costs on the edges into a given number of alm…