Approximation algorithms for hard capacitated \(k\)-facility location problems
From MaRDI portal
Publication:2630091
DOI10.1016/j.ejor.2014.10.011zbMath1341.90080arXiv1311.4759OpenAlexW2963809215MaRDI QIDQ2630091
Shanfei Li, Pieter L. van den Berg, Dion C. Gijswijt, Karen Aardal
Publication date: 25 July 2016
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.4759
Related Items
Multi-level facility location as the maximization of a submodular set function, Improved algorithms for joint optimization of facility locations and network connections, An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation, Approximation algorithms for two variants of correlation clustering problem, LP-based approximation for uniform capacitated facility location problem, Two-phase semi-Lagrangian relaxation for solving the uncapacitated distribution centers location problem for B2C E-commerce, An approximation algorithm for the dynamic facility location problem with outliers, Approximation schemes for \(k\)-facility location, Capacitated facility location with outliers/penalties, A local search approximation algorithm for the uniform capacitated \(k\)-facility location problem, An approximation algorithm for soft capacitated \(k\)-facility location problem, On the cost of essentially fair clusterings, Representative families for matroid intersections, with applications to location, packing, and covering problems, Orientational variable-length strip covering problem: a branch-and-price-based algorithm, A faster FPTAS for knapsack problem with cardinality constraint, Constant-Factor FPT Approximation for Capacitated k-Median, Constant factor approximation algorithm for uniform hard capacitated knapsack median problem, A faster FPTAS for knapsack problem with cardinality constraint
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A 3-approximation algorithm for the facility location problem with uniform capacities
- LP-based approximation algorithms for capacitated facility location
- Analysis of some greedy algorithms for the single-sink fixed-charge transportation problem
- Geometric algorithms and combinatorial optimization
- Structured \(p\)-facility location problems on the line solvable in polynomial time
- Approximation algorithms for knapsack problems with cardinality constraints
- Improved approximation algorithms for capacitated facility location problems
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A new approximation algorithm for the \(k\)-facility location problem
- A constant-factor approximation algorithm for the k -median problem (extended abstract)
- A 5-Approximation for Capacitated Facility Location
- An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- A new greedy approach for facility location problems
- Fast Approximation Algorithms for Knapsack Problems
- An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
- Fast Algorithms for Single-Sink Fixed Charge Transportation Problems with Applications to Manufacturing and Transportation
- Analysis of a Local Search Heuristic for Facility Location Problems
- Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
- Mathematical Programming for Data Mining: Formulations and Challenges
- Approximating min-sum k -clustering in metric spaces
- Approximating k-median via pseudo-approximation
- A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
- Algorithms - ESA 2003
- Algorithms - ESA 2003
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
