Approximability of hard combinatorial optimization problems: an introduction

DOI10.1023/A:1018987015651MaRDI QIDQ1593534zbMATH OpenFDO

Authors Francesco Maffioli, Giulia Galbiati

Publication date 17 January 2001

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/A:1018987015651

zbMATH Keywords

characterization of approximation classescombinatorial optimization problemsintroductory surveyNP-completeness

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Review text

Most combinatorial optimization problems are NP-complete, and therefore in practice approximating methods are impotent. In this introductory survey the authors follow a historical path up to more recent developments in the theoretical characterization of approximation classes. The reader must be familiar with the main concepts of NP-completeness.

Recommendations

• Inapproximability of combinatorial optimization problems
• scientific article; zbMATH DE number 1330033
• Approximate solution of NP optimization problems
• scientific article; zbMATH DE number 1944142
• scientific article; zbMATH DE number 847149

Cited in

(21)

• Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems
• Polynomial approximation algorithms with performance guarantees: an introduction-by-example
• Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes
• Improved approximations for hard optimization problems via problem instance classification
• Inapproximability of combinatorial optimization problems
• scientific article; zbMATH DE number 6832021 (Why is no real title available?)
• scientific article; zbMATH DE number 3873085 (Why is no real title available?)
• On Approximate Solutions for Combinatorial Optimization Problems
• scientific article; zbMATH DE number 4155842 (Why is no real title available?)
• scientific article; zbMATH DE number 3902037 (Why is no real title available?)
• scientific article; zbMATH DE number 1031377 (Why is no real title available?)
• scientific article; zbMATH DE number 1944142 (Why is no real title available?)
• scientific article; zbMATH DE number 1953193 (Why is no real title available?)
• scientific article; zbMATH DE number 1786132 (Why is no real title available?)
• scientific article; zbMATH DE number 1789921 (Why is no real title available?)
• scientific article; zbMATH DE number 2143861 (Why is no real title available?)
• scientific article; zbMATH DE number 780787 (Why is no real title available?)
• Hardness of approximation
• Advances in Combinatorial Optimization
• Set covering approach for reconstruction of sibling relationships
• On simple combinatorial optimization problems. A collection of contributions in honour of Jack van Lint

This page was built for publication: Approximability of hard combinatorial optimization problems: an introduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1593534)