Approximation algorithm for squared metric facility location problem with nonuniform capacities

DOI10.1016/J.DAM.2019.03.013zbMATH Open1422.90047OpenAlexW2935647112WikidataQ128094026 ScholiaQ128094026MaRDI QIDQ2422751FDOQ2422751

Donglei Du, Dongmei Zhang, Yicheng Xu, Dachuan Xu

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

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

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)

Cites Work

• Title not available (Why is that?)
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Neighborhood search heuristics for the uncapacitated facility location problem
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
• A hybrid multistart heuristic for the uncapacitated facility location problem
• A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
• LP-Based Algorithms for Capacitated Facility Location
• Combining (Integer) Linear Programming Techniques and Metaheuristics for Combinatorial Optimization
• Local Search Heuristics for k-Median and Facility Location Problems
• Analysis of a Local Search Heuristic for Facility Location Problems
• On approximate geometric \(k\)-clustering
• A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems
• A local search approximation algorithm for \(k\)-means clustering
• Improved and simplified inapproximability for \(k\)-means

Cited In (3)

• 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
• The approximation gap for the metric facility location problem is not yet closed

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)