Worst-case analysis of the greedy algorithm for a generalization of the maximum p-facility location problem

Worst-case analysis of the greedy algorithm for a generalization of the maximum p-facility location problem

0.00 Avg rating—0 Votes
Article ID: iaor20052054
Country: Netherlands
Volume: 26
Issue: 4
Start Page Number: 193
End Page Number: 197
Publication Date: May 2000
Journal: Operations Research Letters
Authors:
Keywords: heuristics
Abstract:

In this work we consider the maximum p-facility location problem with k additional resource constraints. We prove that the simple greedy algorithm has performance guarantee (1 − e-(k+1))/(k+1).

Reviews

Required fields are marked *. Your email address will not be published.