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)

zbMATH Keywords

NP-completenesscombinatorial optimization problemsintroductory surveycharacterization of approximation classes

Mathematics Subject Classification ID

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

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

(20)

• On simple combinatorial optimization problems. A collection of contributions in honour of Jack van Lint
• scientific article; zbMATH DE number 2143861 (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?)
• Hardness of approximation
• Set covering approach for reconstruction of sibling relationships
• 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
• scientific article; zbMATH DE number 3902037 (Why is no real title available?)
• Improved approximations for hard optimization problems via problem instance classification
• scientific article; zbMATH DE number 1789921 (Why is no real title available?)
• Advances in Combinatorial Optimization
• Inapproximability of combinatorial optimization problems
• scientific article; zbMATH DE number 1786132 (Why is no real title available?)
• On Approximate Solutions for Combinatorial Optimization Problems
• scientific article; zbMATH DE number 780787 (Why is no real title available?)
• scientific article; zbMATH DE number 3873085 (Why is no real title available?)
• scientific article; zbMATH DE number 4155842 (Why is no real title available?)
• scientific article; zbMATH DE number 6832021 (Why is no real title available?)

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)