Approximation algorithm for squared metric facility location problem with nonuniform capacities

DOI10.1016/J.DAM.2019.03.013MaRDI QIDQ2422751zbMATHOpenAlexWikidataFDO

Authors Yicheng Xu, Dongmei Zhang, Dachuan Xu, Donglei Du

Publication date 20 June 2019

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

Full work available at URL https://doi.org/10.1016/j.dam.2019.03.013

zbMATH Keywords

approximation algorithmfacility location problemsquared metricnonuniform capacities

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Recommendations

• A local search approximation algorithm for a squared metric \(k\)-facility location problem
• A local search approximation algorithm for a squared metric \(k\)-facility location problem
• Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties
• Approximation algorithms for the squared metric \(k\)-level facility location problem
• Approximation algorithm for squared metric two-stage stochastic facility location problem

Cites work

• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
• A hybrid multistart heuristic for the uncapacitated facility location problem
• A local search approximation algorithm for \(k\)-means clustering
• An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem
• Analysis of a Local Search Heuristic for Facility Location Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Combining (integer) linear programming techniques and metaheuristics for combinatorial optimization
• Greedy Strikes Back: Improved Facility Location Algorithms
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Improved and simplified inapproximability for \(k\)-means
• LP-based algorithms for capacitated facility location
• Local Search Heuristics for k-Median and Facility Location Problems
• Neighborhood search heuristics for the uncapacitated facility location problem
• Network flows. Theory, algorithms, and applications.
• On approximate geometric \(k\)-clustering

Cited in

(8)

• The approximation gap for the metric facility location problem is not yet closed
• A local search approximation algorithm for a squared metric \(k\)-facility location problem
• Approximation algorithms for the squared metric \(k\)-level facility location problem
• A local search approximation algorithm for a squared metric \(k\)-facility location problem
• Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties
• Improved approximation algorithms for solving the squared metric \(k\)-facility location problem
• Approximation algorithm for squared metric two-stage stochastic facility location problem
• Local search approximation algorithms for the sum of squares facility location problems

This page was built for publication: Approximation algorithm for squared metric facility location problem with nonuniform capacities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2422751)