Heuristics for the fixed cost median problem |
| |
Authors: | Dorit S Hochbaum |
| |
Institution: | (1) Graduate School of Industrial Administration, Carnegie-Mellon University, 15213 Pittsburgh, PA, USA |
| |
Abstract: | We describe in this paper polynomial heuristics for three important hard problems—the discrete fixed cost median problem (the plant location problem), the continuous fixed cost median problem in a Euclidean space, and the network fixed cost median problem with convex costs. The heuristics for all the three problems guarantee error ratios no worse than the logarithm of the number of customer points. The derivation of the heuristics is based on the presentation of all types of median problems discussed as a set covering problem. |
| |
Keywords: | Set Covering Problem Median Problem Location Problems Heuristics Worst Case Analysis Continuous Location Problem |
本文献已被 SpringerLink 等数据库收录! |
|