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]