Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

DOI10.1007/b11961zbMath1279.68358OpenAlexW4298253479MaRDI QIDQ5900928

Yinyu Ye, Mohammad Mahdian, Jia-Wei Zhang

Publication date: 26 May 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b11961

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items

Combinatorial approximation algorithms for the robust facility location problem with penalties ⋮ New approximation algorithms for the unsplittable capacitated facility location problem ⋮ Approximation algorithms for hard capacitated \(k\)-facility location problems ⋮ Approximation algorithms for facility location problems with a special class of subadditive cost functions ⋮ A 3-approximation algorithm for the facility location problem with uniform capacities ⋮ On min-max \(r\)-gatherings ⋮ \(\mathrm{M}^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space ⋮ LP-Based Algorithms for Capacitated Facility Location ⋮ A PTAS for the cardinality constrained covering with unit balls ⋮ The approximation gap for the metric facility location problem is not yet closed ⋮ Approximation algorithms for the robust/soft-capacitated 2-level facility location problems ⋮ Online unit clustering: Variations on a theme ⋮ Approximating soft-capacitated facility location problem with uncertainty ⋮ A splitter location-allocation problem in designing fiber optic access networks ⋮ Improved approximation algorithms for capacitated facility location problems ⋮ Approximating the two-level facility location problem via a quasi-greedy approach ⋮ An approximation algorithm for a facility location problem with stochastic demands and inventories ⋮ On Min-Max r-Gatherings ⋮ An approximation algorithm for stochastic multi-level facility location problem with soft capacities