Euclidean prize-collecting Steiner forest
From MaRDI portal
Publication:2429324
DOI10.1007/S00453-011-9491-8zbMath1241.68086OpenAlexW2096477872MaRDI QIDQ2429324
Mohammad Taghi Hajiaghayi, MohammadHossein Bateni
Publication date: 26 April 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-011-9491-8
Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Related Items (4)
Exact algorithms for budgeted prize-collecting covering subgraph problems ⋮ A PTAS for the geometric connected facility location problem ⋮ Unnamed Item ⋮ A PTAS for the Steiner Forest Problem in Doubling Metrics
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on the prize collecting traveling salesman problem
- The Steiner problem with edge lengths 1 and 2
- A constant-factor approximation algorithm for the \(k\)-MST problem
- Sparsest cuts and concurrent flows in product graphs.
- Embedding tree metrics into low-dimensional Euclidean spaces
- Approximating the Single-Sink Link-Installation Problem in Network Design
- Detecting high log-densities
- Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Assignment problem in content distribution networks
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Dial a Ride from k-Forest
- Euclidean Prize-Collecting Steiner Forest
- Prize-Collecting Steiner Networks via Iterative Rounding
- Multicommodity flow, well-linked terminals, and routing problems
- Saving an epsilon
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- Product Multicommodity Flow in Wireless Networks
- The prize collecting traveling salesman problem
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- A General Approximation Technique for Constrained Forest Problems
- Spanning Trees—Short or Small
- A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
- Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP
- Edge-Disjoint Paths in Planar Graphs with Constant Congestion
- Tighter Bounds for Graph Steiner Tree Approximation
- Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
This page was built for publication: Euclidean prize-collecting Steiner forest
