We describe the semidefinite analog of the vector packing problem, and show that the semidefinite programming relaxations for Maxcut [10] and graph coloring [17] are in this class of problems. We extend a method of Bienstock and Iyengar [5] which was based on ideas from Nesterov [25] to design an algorithm for computing ε-approximate solutions for this class of semidefinite programs. Our algorithm is in the spirit of Klein and Lu [18], and decreases the dependence of the run-time on ε from ε − − 2 to ε − − 1. For sparse graphs, our method is faster than the best specialized interior point methods. A significant feature of our method is that it treats both the Maxcut and the graph coloring problem in a unified manner.