LP-based approximation for uniform capacitated facility location problem

DOI10.1016/J.DISOPT.2022.100723MaRDI QIDQ2172086zbMATH OpenOpenAlexWikidataFDO

Authors Sapna Grover, Neelima Gupta, Samir Khuller

Publication date 15 September 2022

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2022.100723

zbMATH Keywords

approximationcapacitated facility locationLP-roundingcapacitated \(k\) facility location

Mathematics Subject Classification ID

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

Recommendations

• LP-based approximation algorithms for capacitated facility location
• On uniform capacitated \(k\)-median beyond the natural LP relaxation
• LP-based algorithms for capacitated facility location
• On uniform capacitated \(k\)-median beyond the natural LP relaxation
• Integer Programming and Combinatorial Optimization

Cites work

• scientific article; zbMATH DE number 1187151 (Why is no real title available?)
• scientific article; zbMATH DE number 1305496 (Why is no real title available?)
• scientific article; zbMATH DE number 1342123 (Why is no real title available?)
• scientific article; zbMATH DE number 1947060 (Why is no real title available?)
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• scientific article; zbMATH DE number 2086926 (Why is no real title available?)
• scientific article; zbMATH DE number 1833407 (Why is no real title available?)
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A 3-approximation algorithm for the facility location problem with uniform capacities
• A 5-approximation for capacitated facility location
• A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
• A dependent LP-rounding approach for the \(k\)-median problem
• A new approximation algorithm for the \(k\)-facility location problem
• A new greedy approach for facility location problems
• Algorithms - ESA 2003
• An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
• An approximation algorithm for uniform capacitated \(k\)-median problem with \(1+\epsilon\) capacity violation
• An improved approximation algorithm for the hard uniform capacitated \(k\)-median problem
• Analysis of a Local Search Heuristic for Facility Location Problems
• Approximating \(k\)-median with non-uniform capacities
• Approximating capacitated \(k\)-median with \((1 + \epsilon)k\) open facilities
• Approximating k-median via pseudo-approximation
• Approximation algorithms for hard capacitated \(k\)-facility location problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Bi-factor approximation algorithms for hard capacitated \(k\)-median problems
• Centrality of trees for capacitated \(k\)-center
• Constant approximation for capacitated \(k\)-median with \((1+\epsilon)\)-capacity violation
• Constant factor approximation algorithm for uniform hard capacitated knapsack median problem
• 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 Combinatorial Algorithms for Facility Location Problems
• LP-based algorithms for capacitated facility location
• LP-based approximation algorithms for capacitated facility location
• Lagrangian relaxation for the \(k\)-median problem: new insights and continuity properties
• Local Search Heuristics for k-Median and Facility Location Problems
• Local search heuristic for k-median and facility location problems
• On uniform capacitated \(k\)-median beyond the natural LP relaxation
• The Capacitated K-Center Problem
• The matroid median problem

Cited in

(7)

• LP-based approximation algorithms for capacitated facility location
• The \(p/q\)-\texttt{ACTIVE} uncapacitated facility location problem: investigation of the solution space and an LP-fitting heuristic
• An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties
• New approximation algorithms for the unsplittable capacitated facility location problem
• An approximate cost recovery scheme for the \(k\)-product facility location game with penalties
• LP-based algorithms for capacitated facility location
• An LP-rounding based algorithm for a uniform capacitated facility location problem with penalties

This page was built for publication: LP-based approximation for uniform capacitated facility location problem

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