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

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

A. A. Ageev, M. I. Sviridenko

Publication date: 23 November 1999

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00103-1

zbMATH Keywords

polynomial-time approximation algorithmsatisfiability problemperformance guaranteeuncapacitated facility location

Mathematics Subject Classification ID

Discrete location and assignment (90B80)

Related Items (18)

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization ⋮ An optimal streaming algorithm for non-submodular functions maximization on the integer lattice ⋮ Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint ⋮ Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms ⋮ Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations ⋮ Constrained Submodular Maximization via a Nonsymmetric Technique ⋮ A binary search double greedy algorithm for non-monotone DR-submodular maximization ⋮ A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function ⋮ Donation center location problem ⋮ PASS approximation: a framework for analyzing and designing heuristics ⋮ Profit maximization in social networks and non-monotone DR-submodular maximization ⋮ An approximation algorithm for a competitive facility location problem with network effects ⋮ Approximating the two-level facility location problem via a quasi-greedy approach ⋮ Representative families for matroid intersections, with applications to location, packing, and covering problems ⋮ Online Submodular Maximization with Preemption ⋮ A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints ⋮ Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms ⋮ Private non-monotone 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

This page was built for publication: An 0. 828-approximation algorithm for the uncapacitated facility location problem