Displaying similar documents to “Approximation algorithms for integer covering problems via greedy column generation”

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