A probabilistic analysis of the maximal covering location problem
type: Item
instance of: scholarly article
title: A probabilistic analysis of the maximal covering location problem
zbMATH Open document ID: 0778.68046
DOI: 10.1016/0166-218X(93)90006-A
author: Rakesh V. Vohra
author: Nicholas G. Hall
published in: Discrete Applied Mathematics
publication date: 1994-01-04T00:00:00Z
review text: Under a variety of different random models of the maximal covering location problem, we show that the relativ error of a randomly generated solution converges to zero in expectation as problem size grows. We prove similar results for the relative error between the optimal integer and fractional solutions to the problem. Suppose that randomly generated instances of this problem are used to test heuristics. One consequence of our results is that we should expect the mean relative error of a heuristic to be better than that of randomly generated solutions, if the heuristic is to be considered useful.
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 205584
zbMATH Keywords: approximation algorithms
zbMATH Keywords: random models
zbMATH Keywords: relativ error
zbMATH Keywords: heuristics
MaRDI profile type: Publication
cites work: Probabilistic Analysis of a Relaxation for the k-Median Problem
cites work: A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
cites work: Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
cites work: Q4198056
cites work: Q3675519
cites work: Probabilistic analysis of an lp relaxation bound for the steiner problem in networks
cites work: Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
cites work: The Location of Emergency Service Facilities
cites work: Q3824115
cites work: A Probabilistic Analysis of the K-Location Problem
full work available at URL: 0166-218x(93)90006-a
OpenAlex ID: W2025924556
description: scientific article; zbMATH DE number 205584