Approximation Results Toward Nearest Neighbor Heuristic
Jérôme Monnot (2002)
The Yugoslav Journal of Operations Research
Similarity:
Displaying similar documents to “Improved approximation of the general soft-capacitated facility location problem”
Approximation Results Toward Nearest Neighbor Heuristic
Approximation algorithms for integer covering problems via greedy column generation
Y. Crama, J. Van De Klundert (1994)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
Analysis of an approximation algorithm for scheduling indepentent parallel tasks.
Li, Keqin (1999)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
Comparing notions of approximation.
Mario Furnari, Antonio Massarotti (1988)
Stochastica
Similarity:
In this note we discuss some drawbacks of some approaches to the classification of NP-complete optimization problems. Then we analyze the Theory of Analytical Computational Complexity to gain some insight about the notions of approximation and approximate algorithms. We stress the different roles played by these notions within the theories of Analytical and Algebraic Complexity. We finally outline a possible strategy to capture a more useful notion of approximation which is inspired...
An Overview on Polynomial Approximation of NP-Hard Problems
Vangelis Th. Paschos (2009)
The Yugoslav Journal of Operations Research
Similarity:
A Separable Approximation Dynamic Programming Algorithm for Economic Dispatch With Transmission Losses
Pierre Hansen, Nenad Mladenović (2002)
The Yugoslav Journal of Operations Research
Similarity:
Asymptotic differential approximation ratio : definitions, motivations and application to some combinatorial problems
Marc Demange, Vangelis Th. Paschos (1999)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
Primal-dual approximation algorithms for a packing-covering pair of problems
Sofia Kovaleva, Frits C. R. Spieksma (2002)
RAIRO - Operations Research - Recherche Opérationnelle
Similarity:
We consider a special packing-covering pair of problems. The packing problem is a natural generalization of finding a (weighted) maximum independent set in an interval graph, the covering problem generalizes the problem of finding a (weighted) minimum clique cover in an interval graph. The problem pair involves weights and capacities; we consider the case of unit weights and the case of unit capacities. In each case we describe a simple algorithm that outputs a solution to the packing...