On the Average Case Performance of Some Greedy Approximation Algorithms For the Uncapacitated Facility Location Problem

DOI10.1017/S096354830600798XzbMath1170.90465WikidataQ57401490 ScholiaQ57401490MaRDI QIDQ5443801

Abraham D. Flaxman, Alan M. Frieze, Juan Carlos Vera

Publication date: 22 February 2008

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

multiplicative factor

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (1)

An exact cooperative method for the uncapacitated facility location problem

Cites Work

• Heuristics for semirandom graph problems
• The simple plant location problem: Survey and synthesis
• Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem

This page was built for publication: On the Average Case Performance of Some Greedy Approximation Algorithms For the Uncapacitated Facility Location Problem