Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 171, Issue 2, Pages 648-660Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2004.09.026
Keywords
combinatorial optimization; heuristics; supermodular set function; comatroid; performance guarantee
Ask authors/readers for more resources
We consider the problem of minimizing a supermodular set function on comatroid whose special case is the well-known NP-hard minimization p-median problem. The main result of the paper is a tight bound on the performance guarantee of a greedy heuristic for this problem. As a corollary an analog of the Rado-Edmonds theorem for comatroids is obtained. (c) 2004 Published by Elsevier B.V.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available