Improved approximation of the general 
soft-capacitated facility location problem

Laurent Alfandari

The search session has expired. Please query the service again.

Displaying similar documents to “Improved approximation of the general soft-capacitated facility location problem”

Approximation Results Toward Nearest Neighbor Heuristic

Jérôme Monnot (2002)

The Yugoslav Journal of Operations Research

Similarity:

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