Improved approximation algorithms for the facility location problems with linear/submodular penalties
From MaRDI portal
Publication:747629
DOI10.1007/s00453-014-9911-7zbMath1322.90045OpenAlexW2062310236MaRDI QIDQ747629
Yu Li, Dong-lei Du, Da-Chuan Xu, Nai-Hua Xiu
Publication date: 19 October 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-014-9911-7
Numerical mathematical programming methods (65K05) Discrete location and assignment (90B80) Approximation algorithms (68W25)
Related Items (27)
An approximation algorithm for the \(n\)th power metric facility location problem with linear penalties ⋮ An approximation algorithm for submodular hitting set problem with linear penalties ⋮ An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution ⋮ Local Search Algorithms for k-Median and k-Facility Location Problems with Linear Penalties ⋮ A $$(5.83+\epsilon )$$ ( 5.83 + ϵ ) -Approximation Algorithm for Universal Facility Location Problem with Linear Penalties ⋮ Fractional 0-1 programming and submodularity ⋮ A note on LP-based approximation algorithms for capacitated facility location problem ⋮ Local search approximation algorithms for the \(k\)-means problem with penalties ⋮ Approximation algorithms for the fault-tolerant facility location problem with penalties ⋮ Approximation algorithms for prize-collecting capacitated network design problems ⋮ An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees ⋮ Approximation algorithms for the fault-tolerant facility location problem with submodular penalties ⋮ The facility location problem with maximum distance constraint ⋮ An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions ⋮ A combinatorial approximation algorithm for \(k\)-level facility location problem with submodular penalties ⋮ Unnamed Item ⋮ Local search algorithm for the squared metric \(k\)-facility location problem with linear penalties ⋮ Local search algorithm for universal facility location problem with linear penalties ⋮ Approximation algorithms for the robust facility leasing problem ⋮ Approximating the \(\tau\)-relaxed soft capacitated facility location problem ⋮ An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme ⋮ A note on the submodular vertex cover problem with submodular penalties ⋮ An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties ⋮ An approximation algorithm for the \(k\)-level facility location problem with outliers ⋮ Approximation algorithms for the multiprocessor scheduling with submodular penalties ⋮ Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties ⋮ Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for supply chain planning and logistics problems with market choice
- Approximation algorithms for soft-capacitated facility location in capacitated network design
- An improved approximation algorithm for uncapacitated facility location problem with penalties
- An LP rounding algorithm for approximating uncapacitated facility location problem with penalties
- A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem
- A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties
- A 1.488 approximation algorithm for the uncapacitated facility location problem
- A new approximation algorithm for the \(k\)-facility location problem
- A primal-dual approximation algorithm for the facility location problem with submodular penalties
- Approximating the two-level facility location problem via a quasi-greedy approach
- Submodular functions and optimization.
- Improved Approximation Algorithm for k-Level UFL with Penalties, a Simplistic View on Randomizing the Scaling Parameter
- Approximation Algorithms for Metric Facility Location Problems
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- An approximation scheme for stochastic linear programming and its application to stochastic integer programs
- 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
- Greedy Strikes Back: Improved Facility Location Algorithms
- Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
- Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem
- Improved Approximation Algorithms for the Facility Location Problems with Linear/submodular Penalty
- Stochastic Transportation-Inventory Network Design Problem
- A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
- An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
This page was built for publication: Improved approximation algorithms for the facility location problems with linear/submodular penalties
