Primal-dual algorithms for connected facility location problems
A Connected Facility Location problem (ConFL) generalizes FL-problems by additionally requiring the connectivity of the open facilities by a Steiner tree \(T\) yielding an extra cost of \(M\times\text{cost}(T)\); here \(M\) is an external factor due to the specific requirements for Steiner edges (f.e. connecting hubs). The authors propose constant factor approximation algorithms based on the primal-dual scheme, where simultaneously an integer primal solution and a solution of the dual of its linear programming relaxation are determined. In a first phase it is decided which facilities to open (by aggregating at least \(M\) demand) and which part of the cost should incurred to the Steiner tree portion of the dual solution. The second phase constructs a Steiner tree or an approximate one in polynomial time. Altogether, the paper shows certain constant factor approximations for ConFL as well as for the connected \(k\)-median problem (ConFL, where at most \(k\) facilities are allowed to open) and for special cases (f.e. \(M= 1\)).
- scientific article; zbMATH DE number 1947062
- Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem
- A 6.55 factor primal-dual approximation algorithm for the connected facility location problem
- Approximation algorithms for connected facility location problems
- A primal-dual approximation algorithm for the facility location problem with submodular penalties
- Dual-based local search for the connected facility location and related problems
- Approximation Algorithms for Single and Multi-Commodity Connected Facility Location
- scientific article; zbMATH DE number 3885614
- Improved Approximation Algorithm for Connected Facility Location Problems
- Approximate the lower-bounded connected facility location problem
- Approximation algorithms for connected facility location 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
- The p-arborescence star problem: formulations and exact solution approaches
- A quadratic time exact algorithm for continuous connected 2-facility location problem in trees
- Black-box reductions for cost-sharing mechanism design
- An algorithmic framework for the exact solution of tree-star problems
- General network design: a unified view of combined location and network design problems
- Connected facility location via random facility sampling and core detouring
- Algorithms for the metric ring star problem with fixed edge-cost ratio
- Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty
- A PTAS for the geometric connected facility location problem
- Optimal data placement on networks with a constant number of clients
- A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
- Hedging uncertainty: approximation algorithms for stochastic optimization problems
- Approximate the lower-bounded connected facility location problem
- Dual-based local search for the connected facility location and related problems
- A quadratic time exact algorithm for continuous connected 2-facility location problem in trees (extended abstract)
- Approximate robust optimization for the connected facility location problem
- Approximation Algorithms for Single and Multi-Commodity Connected Facility Location
- Combinatorial approximation algorithms for buy-at-bulk connected facility location problems
- Benders decomposition of the passive optical network design problem
- LP-based approximation algorithms for facility location in buy-at-bulk network design
- Routing under uncertainty: the \textit{a priori} traveling repairman problem
- Improved Approximation Algorithm for Connected Facility Location Problems
- scientific article; zbMATH DE number 1947062 (Why is no real title available?)
- Approximation algorithms for a combined facility location buy-at-bulk network design problem
- Connected fair domination in graphs
- Construction Line Algorithms for the Connection Location-Allocation Problem
- The online connected facility location problem
- Deterministic sampling algorithms for network design
- Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem
- Black-box reductions for cost-sharing mechanism design
- Branch‐and‐cut algorithms for the ‐arborescence star problem
- Approximation algorithms for prize-collecting capacitated network design problems
- Approximation schemes for k-facility location
- An exact algorithm for the maximum leaf spanning tree problem
- A branch-and-cut approach to solve the fault diagnosis problem with lazy spread and imperfect system information
- A PTAS framework for clustering problems in doubling metrics
- Branch-and-cut-and-price for capacitated connected facility location
- Minimum connected dominating set and backbone of a random graph
- LP-based approximation algorithms for facility location in buy-at-bulk network design
- A polynomial-time exact algorithm for the connected k-facility location problem on trees
- MIP models for connected facility location: a theoretical and computational study
- The A priori traveling repairman problem
- On the connected minimum sum of radii problem
- A poly-log approximation for transaction scheduling in fog-cloud computing and beyond
- A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem
- Solving connected dominating set faster than \(2^n\)
This page was built for publication: Primal-dual algorithms for connected facility location problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1884770)
