An 0. 828-approximation algorithm for the uncapacitated facility location problem

DOI10.1016/S0166-218X(99)00103-1zbMath0932.90019MaRDI QIDQ1296569

A. A. Ageev, M. I. Sviridenko

Publication date: 23 November 1999

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

zbMATH Keywords

polynomial-time approximation algorithm; satisfiability problem; performance guarantee; uncapacitated facility location

Mathematics Subject Classification ID

90B80: Discrete location and assignment

Related Items

Unnamed Item, Online Submodular Maximization with Preemption, Constrained Submodular Maximization via a Nonsymmetric Technique, Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms, An approximation algorithm for a competitive facility location problem with network effects, Donation center location problem, PASS approximation: a framework for analyzing and designing heuristics, Representative families for matroid intersections, with applications to location, packing, and covering problems, Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint, A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function, Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms, Approximating the two-level facility location problem via a quasi-greedy approach, A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization

Cites Work

• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Unnamed Item
• Unnamed Item