Displaying similar documents to “An Overview on Polynomial Approximation of NP-Hard Problems”

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,...

Differential approximation of NP-hard problems with equal size feasible solutions

Jérôme Monnot (2002)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem π which only differ on a linear transformation of their objective functions. This...

Improved approximation of the general soft-capacitated facility location problem

Laurent Alfandari (2007)

RAIRO - Operations Research

Similarity:

The soft-capacitated facility location problem, where each facility is composed of a variable number of fixed-capacity production units, has been recently studied in several papers, especially in the metric case. In this paper, we only consider the general problem where connection costs do not systematically satisfy the triangle inequality property. We show that an adaptation of the set covering greedy heuristic, where the subproblem is approximately solved by a fully polynomial-time...

Greedy Algorithms for Adaptive Approximation

Albert Cohen (2009)

Bollettino dell'Unione Matematica Italiana

Similarity:

We discuss the performances of greedy algorithms for two problems of numerical approximation. The first one is the best approximation of an arbitrary function by an N-terms linear combination of simple functions adaptively picked within a large dictionary. The second one is the approximation of an arbitrary function by a piecewise polynomial function on an optimally adapted triangulation of cardinality N. Performance is measured in terms of convergence rate with respect to the number...