Designing high-quality approximation algorithms for combinatorial optimization problems

For NP-hard combinatorial optimization problems, approximation algorithms w ith high performances have been proposed. In many of these algorithms, math ematical programming techniques have been used and proved to be very useful . In this survey, we present recent mathematical programming techniques as well as classic fundamental techniques, by showing how these techniques are used in designing high-quality approximation algorithms for NP-hard combin atorial optimization problems.