In this project, we focus on combinatorial optimization on graphs. The rapid growth of the Internet, the widespread deployment of sensors and scientific advances have resulted in more and more data sets. Many data sets can be modelled as graphs, and many applications involve solving combinatorial optimization problems on graphs.