Primal-dual algorithms for connected facility location problems
From MaRDI portal
Publication:1884770
DOI10.1007/s00453-004-1112-3zbMath1108.90026OpenAlexW2147879413MaRDI QIDQ1884770
Publication date: 5 November 2004
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-004-1112-3
Facility locationSteiner treesApproximation algorithmsPrimal-dual algorithmsConnected facility location
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
The \(p\)-arborescence star problem: formulations and exact solution approaches ⋮ Approximate robust optimization for the connected facility location problem ⋮ A quadratic time exact algorithm for continuous connected 2-facility location problem in trees ⋮ LP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design ⋮ Routing Under Uncertainty: The a priori Traveling Repairman Problem ⋮ Combinatorial approximation algorithms for buy-at-bulk connected facility location problems ⋮ Benders decomposition of the passive optical network design problem ⋮ A PTAS for the geometric connected facility location problem ⋮ General network design: a unified view of combined location and network design problems ⋮ Branch‐and‐cut algorithms for the ‐arborescence star problem ⋮ Approximation algorithms for prize-collecting capacitated network design problems ⋮ A Quadratic Time Exact Algorithm for Continuous Connected 2-Facility Location Problem in Trees (Extended Abstract) ⋮ Approximation schemes for \(k\)-facility location ⋮ Connected Fair Domination in Graphs ⋮ Dynamic vs. oblivious routing in network design ⋮ Approximate the lower-bounded connected facility location problem ⋮ Connected facility location via random facility sampling and core detouring ⋮ An exact algorithm for the maximum leaf spanning tree problem ⋮ Optimal data placement on networks with a constant number of clients ⋮ Branch-and-cut-and-price for capacitated connected facility location ⋮ LP-based approximation algorithms for facility location in buy-at-bulk network design ⋮ Black-box reductions for cost-sharing mechanism design ⋮ Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems ⋮ Approximation Algorithms for Single and Multi-Commodity Connected Facility Location ⋮ A simpler and better derandomization of an approximation algorithm for single source rent-or-buy ⋮ An algorithmic framework for the exact solution of tree-star problems ⋮ Solving connected dominating set faster than \(2^n\) ⋮ Approximation Algorithms for a Combined Facility Location Buy-at-Bulk Network Design Problem ⋮ Deterministic sampling algorithms for network design ⋮ MIP models for connected facility location: a theoretical and computational study ⋮ Hedging uncertainty: approximation algorithms for stochastic optimization problems ⋮ Computing a tree having a small vertex cover ⋮ The A priori traveling repairman problem ⋮ A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem ⋮ Algorithms for the metric ring star problem with fixed edge-cost ratio ⋮ Approximation algorithms for connected facility location problems ⋮ Approximation algorithms for connected maximum cut and related problems ⋮ Approximation algorithms for soft-capacitated facility location in capacitated network design ⋮ A 6.55 factor primal-dual approximation algorithm for the connected facility location problem ⋮ Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty ⋮ Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem ⋮ Unnamed Item
