Designing High-Quality Approximation Algorithms for Combinatorial Optimization Problems

Takao ASANO  Kenichiro IWAMA  Hideyuki TAKADA  Yoshiko YAMASHITA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E83-D   No.3   pp.462-479
Publication Date: 2000/03/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: Approximate Algorithms for Combinatorial Problems
Keyword: 
dynamic programming,  linear programming relaxation,  primal dual method,  scaling,  semidefinite programming,  

Full Text: PDF(767.3KB)>>
Buy this Article



Summary: 
For NP-hard combinatorial optimization problems, approximation algorithms with high performances have been proposed. In many of these algorithms, mathematical 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 combinatorial optimization problems.