Combinatorial Optimization

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


  • 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


  • 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]