# Combinatorial Optimization¶

Just a few references with relevant keywords to be developed later.

Basics

*Introduction to Algorithms*[T2]divide-and-conquer, dynamic programming,**greedy algorithms**, graph algorithms*Combinatorial Optimization*[T1]flow problems, TSP,**matroids**& the greedy algorithm

Approximation algorithms

*The Design of Approximation Algorithms*[T8]greedy algorithms & local search, deterministic and randomized**rounding**of linear or**semidefinite programs**, primal-dual method*Approximation Algorithms*[T7]…- … [wikipedia]
**branch and bound**

Miscellaneous

- Goemans et Williamson,
**Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming**, 1995, doi:10.1145/227683.227684, [48] -A randomized algorithm for MAXCUT based on a semi-definite programming relaxation of the original problem combined with a probabilistic rounding technique that yields a high probability approximate solution that has an approximation ratio of about 0.878. - Gonçalves et al.,
**Biased random-key genetic algorithms for combinatorial optimization**, 2011, doi:10.1007/s10732-010-9143-1, [50]