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

DOI10.1051/RO:1999121zbMATH Open0961.90084OpenAlexW2033893726MaRDI QIDQ4497873FDOQ4497873

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

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
• Probabilistic asymptotic properties of some combinatorial optimization problems
• On Approximate Solutions for Combinatorial Optimization Problems

zbMATH Keywords

complexitybin packingcoveringcoloringNP-complete problempolynomial time approximation algorithm

Mathematics Subject Classification ID

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

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)