Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems

DOI10.1051/RO:1999121MaRDI QIDQ4497873zbMATH OpenOpenAlexFDO

Authors Marc Demange, Vangelis Th. Paschos

Publication date 24 August 2000

Published in RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/197785, https://semanticscholar.org/paper/3f17ebbb2c963e3767affe63ca3f977cb944c6b1

zbMATH Keywords

complexitybin packingcoveringcoloringNP-complete problempolynomial time approximation algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Differential approximation algorithms for some combinatorial optimization problems
• Approximating a class of combinatorial problems with rational objective function
• Approximation schemes for subset-sums ratio problems
• scientific article; zbMATH DE number 1789921
• Remarks on an asymptotic method in combinatorics
• Approximation schemes for subset sum ratio problems
• scientific article; zbMATH DE number 4167872
• Probabilistic asymptotic properties of some combinatorial optimization problems
• On Approximate Solutions for Combinatorial Optimization Problems

Cited in

(1)

• A survey on the structure of approximation classes

This page was built for publication: Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems

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