Euclidean prize-collecting Steiner forest
From MaRDI portal
Publication:2429324
DOI10.1007/S00453-011-9491-8zbMATH Open1241.68086OpenAlexW2096477872MaRDI QIDQ2429324FDOQ2429324
Authors: Mohammad T. 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
Recommendations
- Euclidean Prize-Collecting Steiner Forest
- A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
- scientific article; zbMATH DE number 6783450
- Elementary approximation algorithms for prize collecting Steiner tree problems
- Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Network design and communication in computer systems (68M10)
Cites Work
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- The prize collecting traveling salesman problem
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- A General Approximation Technique for Constrained Forest Problems
- Tighter Bounds for Graph Steiner Tree Approximation
- A note on the prize collecting traveling salesman problem
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Title not available (Why is that?)
- Assignment problem in content distribution networks, unsplittable hard-capacitated facility location
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
- Prize-collecting Steiner networks via iterative rounding
- Spanning Trees—Short or Small
- The Steiner problem with edge lengths 1 and 2
- Multicommodity flow, well-linked terminals, and routing problems
- Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- Dial a Ride from k-Forest
- Sparsest cuts and concurrent flows in product graphs.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth
- Approximation algorithms for prize collecting forest problems with submodular penalty functions
- A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
- Edge-disjoint paths in planar graphs with constant congestion
- Approximating the single-sink link-installation problem in network design
- Title not available (Why is that?)
- A constant-factor approximation algorithm for the \(k\)-MST problem
- Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
- Embedding tree metrics into low-dimensional Euclidean spaces
- Euclidean Prize-Collecting Steiner Forest
- Product Multicommodity Flow in Wireless Networks
Cited In (9)
- Streaming algorithms for geometric Steiner forest
- Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth
- Euclidean Prize-Collecting Steiner Forest
- A PTAS for the Steiner forest problem in doubling metrics
- Colored Non-crossing Euclidean Steiner Forest
- Exact algorithms for budgeted prize-collecting covering subgraph problems
- A unified PTAS for prize collecting TSP and Steiner tree problem in doubling metrics
- A PTAS for the geometric connected facility location problem
- A unified PTAS for prize collecting TSP and Steiner tree problem in doubling metrics
This page was built for publication: Euclidean prize-collecting Steiner forest
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2429324)
