Connected facility location via random facility sampling and core detouring
From MaRDI portal
Publication:1959419
DOI10.1016/j.jcss.2010.02.001zbMath1208.68236OpenAlexW2060329104MaRDI QIDQ1959419
Friedrich Eisenbrand, Fabrizio Grandoni, Thomas Rothvoß, Guido Schäfer
Publication date: 7 October 2010
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2010.02.001
Discrete location and assignment (90B80) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (18)
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 ⋮ A cutting plane algorithm for the capacitated connected facility location problem ⋮ APPROXIMATION ALGORITHMS FOR BUY-AT-BULK GEOMETRIC NETWORK DESIGN ⋮ A Quadratic Time Exact Algorithm for Continuous Connected 2-Facility Location Problem in Trees (Extended Abstract) ⋮ LP-based approximation algorithms for facility location in buy-at-bulk network design ⋮ Approximation Algorithms for Single and Multi-Commodity Connected Facility Location ⋮ An algorithmic framework for the exact solution of tree-star problems ⋮ Approximation Algorithms for a Combined Facility Location Buy-at-Bulk Network Design Problem ⋮ A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design ⋮ 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 ⋮ Lagrangian decompositions for the two-level FTTx network design problem ⋮ Algorithms for the metric ring star problem with fixed edge-cost ratio ⋮ The incremental connected facility location problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The Steiner problem with edge lengths 1 and 2
- Primal-dual algorithms for connected facility location problems
- A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
- Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree
- Proof verification and the hardness of approximation problems
- A Dynamic Programming Approach to Sequencing Problems
- Approximation Algorithms for Problems Combining Facility Location and Network Design
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
- New Approaches for Virtual Private Network Design
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Deterministic Sampling Algorithms for Network Design
- Approximation via cost sharing
- Boosted sampling
- Simpler and better approximation algorithms for network design
- The Traveling Salesman Problem with Distances One and Two
- A General Approximation Technique for Constrained Forest Problems
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- A constant factor approximation for the single sink edge installation problems
- Provisioning a virtual private network
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Algorithm Theory - SWAT 2004
- Improved Approximation for Single-Sink Buy-at-Bulk
- Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem
- The steiner problem in graphs
- Automata, Languages and Programming
This page was built for publication: Connected facility location via random facility sampling and core detouring
