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

DOI10.1016/S0166-218X(99)00103-1zbMATH Open0932.90019OpenAlexW1998735557MaRDI QIDQ1296569FDOQ1296569

Alexander Ageev, Maxim 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

Recommendations

• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• An approximation algorithm for the maximization version of the two level uncapacitated facility location problem
• scientific article
• scientific article; zbMATH DE number 1303608

zbMATH Keywords

satisfiability problempolynomial-time approximation algorithmperformance guaranteeuncapacitated facility location

Mathematics Subject Classification ID

Discrete location and assignment (90B80)

Cites Work

• Title not available (Why is that?)
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Title not available (Why is that?)

Cited In (27)

• Profit maximization in social networks and non-monotone DR-submodular maximization
• An optimal streaming algorithm for non-submodular functions maximization on the integer lattice
• Title not available (Why is that?)
• Adaptive algorithms on maximizing monotone nonsubmodular functions
• Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms
• A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints
• An approximation algorithm for a competitive facility location problem with network effects
• Representative families for matroid intersections, with applications to location, packing, and covering problems
• Title not available (Why is that?)
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
• An approximation algorithm for the maximization version of the two level uncapacitated facility location problem
• An acceleration of Erlenkotter-Körkel's algorithms for the uncapacitated facility location problem
• Online Submodular Maximization with Preemption
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
• Approximating the two-level facility location problem via a quasi-greedy approach
• A binary search double greedy algorithm for non-monotone DR-submodular maximization
• Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations
• On the approximation of the minimum disturbance \(p\)-facility location problem
• Donation center location problem
• Constrained Submodular Maximization via a Nonsymmetric Technique
• Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms
• PASS approximation: a framework for analyzing and designing heuristics
• A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function
• A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
• Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Private non-monotone submodular maximization

This page was built for publication: An 0. 828-approximation algorithm 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 Q1296569)