For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Designing High-Quality Approximation Algorithms for Combinatorial Optimization Problems
Takao ASANO Kenichiro IWAMA Hideyuki TAKADA Yoshiko YAMASHITA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/03/25
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: Approximate Algorithms for Combinatorial Problems
dynamic programming, linear programming relaxation, primal dual method, scaling, semidefinite programming,
Full Text: PDF(767.3KB)>>
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.