Primal-dual algorithms for connected facility location problems

From MaRDI portal
Publication:1884770

DOI10.1007/s00453-004-1112-3zbMath1108.90026OpenAlexW2147879413MaRDI QIDQ1884770

Chaitanya Swamy, Amit Kumar

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




Related Items

The \(p\)-arborescence star problem: formulations and exact solution approachesApproximate robust optimization for the connected facility location problemA quadratic time exact algorithm for continuous connected 2-facility location problem in treesLP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network DesignRouting Under Uncertainty: The a priori Traveling Repairman ProblemCombinatorial approximation algorithms for buy-at-bulk connected facility location problemsBenders decomposition of the passive optical network design problemA PTAS for the geometric connected facility location problemGeneral network design: a unified view of combined location and network design problemsBranch‐and‐cut algorithms for the ‐arborescence star problemApproximation algorithms for prize-collecting capacitated network design problemsA Quadratic Time Exact Algorithm for Continuous Connected 2-Facility Location Problem in Trees (Extended Abstract)Approximation schemes for \(k\)-facility locationConnected Fair Domination in GraphsDynamic vs. oblivious routing in network designApproximate the lower-bounded connected facility location problemConnected facility location via random facility sampling and core detouringAn exact algorithm for the maximum leaf spanning tree problemOptimal data placement on networks with a constant number of clientsBranch-and-cut-and-price for capacitated connected facility locationLP-based approximation algorithms for facility location in buy-at-bulk network designBlack-box reductions for cost-sharing mechanism designFacility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency ProblemsApproximation Algorithms for Single and Multi-Commodity Connected Facility LocationA simpler and better derandomization of an approximation algorithm for single source rent-or-buyAn algorithmic framework for the exact solution of tree-star problemsSolving connected dominating set faster than \(2^n\)Approximation Algorithms for a Combined Facility Location Buy-at-Bulk Network Design ProblemDeterministic sampling algorithms for network designMIP models for connected facility location: a theoretical and computational studyHedging uncertainty: approximation algorithms for stochastic optimization problemsComputing a tree having a small vertex coverThe A priori traveling repairman problemA randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problemAlgorithms for the metric ring star problem with fixed edge-cost ratioApproximation algorithms for connected facility location problemsApproximation algorithms for connected maximum cut and related problemsApproximation algorithms for soft-capacitated facility location in capacitated network designA 6.55 factor primal-dual approximation algorithm for the connected facility location problemApproximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penaltyImproved Primal-Dual Approximation Algorithm for the Connected Facility Location ProblemUnnamed Item