A probabilistic analysis of the maximal covering location problem

DOI10.1016/0166-218X(93)90006-AzbMath0778.68046OpenAlexW2025924556MaRDI QIDQ1801679

Rakesh V. Vohra, Nicholas G. Hall

Publication date: 4 January 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)90006-a

zbMATH Keywords

heuristicsapproximation algorithmsrandom modelsrelativ error

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (9)

A Branch-and-Cut Algorithm for Submodular Interdiction Games ⋮ The multimode covering location problem ⋮ An exact method for constrained maximization of the conditional value-at-risk of a class of stochastic submodular functions ⋮ Tight Approximation Bounds for the Seminar Assignment Problem ⋮ Optimal approximability of bookmark assignments ⋮ Probabilistic Partial Set Covering with an Oracle for Chance Constraints ⋮ Cut problems in graphs with a budget constraint ⋮ Multimode extensions of combinatorial optimization problems ⋮ Improved approximation of maximum vertex cover

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• A Probabilistic Analysis of the K-Location Problem
• Probabilistic Analysis of a Relaxation for the k-Median Problem
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Probabilistic analysis of an lp relaxation bound for the steiner problem in networks
• The Location of Emergency Service Facilities
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: A probabilistic analysis of the maximal covering location problem