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

DOI10.1016/S0167-6377(00)00022-5zbMath0971.90044MaRDI QIDQ1577475

M. I. Sviridenko

Publication date: 22 November 2000

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmworst-case analysisGreedy algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Discrete location and assignment (90B80)

Cites Work

• Unnamed Item
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• A threshold of ln n for approximating set cover
• An O(n) algorithm for the multiple-choice knapsack linear program
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• An analysis of approximations for maximizing submodular set functions—I

This page was built for publication: Worst-case analysis of the greedy algorithm for a generalization of the maximum \(p\)-facility location problem