Designing High-Quality Approximation Algorithms for Combinatorial Optimization Problems
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E83-D No.3 pp.462-479
- Publication Date
- 2000/03/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- INVITED SURVEY PAPER
- Category
- Approximate Algorithms for Combinatorial Problems
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takao ASANO, Kenichiro IWAMA, Hideyuki TAKADA, Yoshiko YAMASHITA, "Designing High-Quality Approximation Algorithms for Combinatorial Optimization Problems" in IEICE TRANSACTIONS on Information,
vol. E83-D, no. 3, pp. 462-479, March 2000, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_3_462/_p
Copy
@ARTICLE{e83-d_3_462,
author={Takao ASANO, Kenichiro IWAMA, Hideyuki TAKADA, Yoshiko YAMASHITA, },
journal={IEICE TRANSACTIONS on Information},
title={Designing High-Quality Approximation Algorithms for Combinatorial Optimization Problems},
year={2000},
volume={E83-D},
number={3},
pages={462-479},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={March},}
Copy
TY - JOUR
TI - Designing High-Quality Approximation Algorithms for Combinatorial Optimization Problems
T2 - IEICE TRANSACTIONS on Information
SP - 462
EP - 479
AU - Takao ASANO
AU - Kenichiro IWAMA
AU - Hideyuki TAKADA
AU - Yoshiko YAMASHITA
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E83-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2000
AB - 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.
ER -
English
