An ex-post bound on the greedy heuristic for the uncapacitated facility location problem

DOI10.1051/RO:2006016MaRDI QIDQ3411298zbMATH OpenOpenAlexFDO

Authors Jean-Michel Thizy

Publication date 11 December 2006

Published in RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=RO_2006__40_2_143_0, https://eudml.org/doc/105341, https://semanticscholar.org/paper/973d1aafdab18a7aacb3d53a6ad661255bc0b831

zbMATH Keywords

boundfacility location problemgreedy heuristic

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Mixed integer programming (90C11)

Recommendations

• Worst-case analysis of the greedy algorithm for a generalization of the maximum \(p\)-facility location problem
• On the Average Case Performance of Some Greedy Approximation Algorithms For the Uncapacitated Facility Location Problem
• scientific article; zbMATH DE number 1303608
• An 0. 828-approximation algorithm for the uncapacitated facility location problem
• Greedy Strikes Back: Improved Facility Location Algorithms

Cites work

• A Dual-Based Procedure for Uncapacitated Facility Location
• A Greedy Heuristic for the Set-Covering Problem
• A man-machine approach toward solving the traveling salesman problem
• A New Algorithm for Locating Sources Among Destinations
• A Primal Approach to the Simple Plant Location Problem
• An analysis of approximations for maximizing submodular set functions—I
• An analysis of the greedy algorithm for the submodular set covering problem
• Approximation algorithms for combinatorial problems
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• scientific article; zbMATH DE number 4202014 (Why is no real title available?)
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 3561083 (Why is no real title available?)
• scientific article; zbMATH DE number 3559283 (Why is no real title available?)
• scientific article; zbMATH DE number 3566547 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• Note—On “Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms”
• On the Greedy Heuristic for Continuous Covering and Packing Problems
• Probabilistic Analysis of a Relaxation for the k-Median Problem

Cited in

(3)

• Worst-case analysis of the greedy algorithm for a generalization of the maximum \(p\)-facility location problem
• scientific article; zbMATH DE number 5872754 (Why is no real title available?)
• The \(p/q\)-\texttt{ACTIVE} uncapacitated facility location problem: investigation of the solution space and an LP-fitting heuristic

This page was built for publication: An ex-post bound on the greedy heuristic for the uncapacitated facility location problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3411298)