Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems
Marc Demange, Vangelis Th. Paschos (2010)
RAIRO - Operations Research
Similarity:
We first motivate and define a notion of asymptotic differential approximation ratio. For this, we introduce a new class of problems called radial problems including in particular the hereditary ones. Next, we validate the definition of the asymptotic differential approximation ratio by proving positive, conditional and negative approximation results for some combinatorial problems. We first derive a differential approximation analysis of a classical greedy algorithm for bin packing,...