An improved LP-based approximation for steiner tree
From MaRDI portal
Publication:2875185
DOI10.1145/1806689.1806769zbMath1293.05039OpenAlexW1991055327WikidataQ56288513 ScholiaQ56288513MaRDI QIDQ2875185
Jaroslaw Byrka, Thomas Rothvoß, Fabrizio Grandoni, Laura Sanità
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://infoscience.epfl.ch/record/148220/files/SteinerTree-STOC2010.pdf
Trees (05C05) Linear programming (90C05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (59)
The Steiner Problem for Count Matroids ⋮ Approximation algorithms for stochastic combinatorial optimization problems ⋮ Minimum Certificate Dispersal with Tree Structures ⋮ From Cost Sharing Mechanisms to Online Selection Problems ⋮ Combinatorial approximation algorithms for buy-at-bulk connected facility location problems ⋮ Computing optimal Steiner trees in polynomial space ⋮ A general approximation method for bicriteria minimization problems ⋮ Competitive and deterministic embeddings of virtual networks ⋮ On the low-dimensional Steiner minimum tree problem in Hamming metric ⋮ Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound ⋮ On the approximability of dense Steiner problems ⋮ Exponential approximation schemata for some network design problems ⋮ Connecting guards with minimum Steiner points inside simple polygons ⋮ An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2 ⋮ New approaches to multi-objective optimization ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ Steiner connectivity problems in hypergraphs ⋮ Robust Algorithms for TSP and Steiner Tree ⋮ A polylogarithmic approximation for computing non-metric terminal Steiner trees ⋮ Two-stage robust network design with exponential scenarios ⋮ Improved approximation algorithms for directed Steiner forest ⋮ Energy-efficient communication in multi-interface wireless networks ⋮ A PTAS for the Steiner Forest Problem in Doubling Metrics ⋮ Strategyproof auction mechanisms for network procurement ⋮ Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ On the edge capacitated Steiner tree problem ⋮ Network design with a discrete set of traffic matrices ⋮ Bounding the payment of approximate truthful mechanisms ⋮ Designing cost-sharing methods for Bayesian games ⋮ Algorithms for the minimum diameter terminal Steiner tree problem ⋮ Definition and algorithms for reliable Steiner tree problem ⋮ The expanding search ratio of a graph ⋮ Online covering salesman problem ⋮ Approximation Algorithms for Single and Multi-Commodity Connected Facility Location ⋮ On the Low-Dimensional Steiner Minimum Tree Problem in Hamming Metric ⋮ An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity ⋮ Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs ⋮ Approximating the \(k\)-splittable capacitated network design problem ⋮ Bottleneck Steiner tree with bounded number of Steiner vertices ⋮ Approximation Algorithms for a Combined Facility Location Buy-at-Bulk Network Design Problem ⋮ The Euclidean bottleneck full Steiner tree problem ⋮ Exact and approximate equilibria for optimal group network formation ⋮ A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs ⋮ Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem ⋮ Designing Networks with Good Equilibria under Uncertainty ⋮ Algorithms for the metric ring star problem with fixed edge-cost ratio ⋮ Travelling on graphs with small highway dimension ⋮ Designing Cost-Sharing Methods for Bayesian Games ⋮ Approximating fault-tolerant group-Steiner problems ⋮ New Reoptimization Techniques applied to Steiner Tree Problem ⋮ Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty ⋮ \(1\)-line minimum rectilinear Steiner trees and related problems ⋮ Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE ⋮ Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree ⋮ Unnamed Item ⋮ On the Clustered Steiner Tree Problem ⋮ Approximability of minimum certificate dispersal with tree structures ⋮ On the clustered Steiner tree problem
This page was built for publication: An improved LP-based approximation for steiner tree
