A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
From MaRDI portal
Publication:4512573
DOI10.1006/jagm.2000.1096zbMath0962.68136OpenAlexW2610052675MaRDI QIDQ4512573
Goran Konjevod, R. Ravi, Naveen Garg
Publication date: 5 November 2000
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.2000.1096
Related Items (57)
Bounded Degree Group Steiner Tree Problems ⋮ $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm ⋮ On approximating degree-bounded network design problems ⋮ A random-key genetic algorithm for the generalized traveling salesman problem ⋮ GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem ⋮ On some network design problems with degree constraints ⋮ An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties ⋮ Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems ⋮ Online Buy-at-Bulk Network Design ⋮ A Spectral Approach to Network Design ⋮ A transformation technique for the clustered generalized traveling salesman problem with applications to logistics ⋮ A polylogarithmic approximation for computing non-metric terminal Steiner trees ⋮ \(k\)-Transmitter watchman routes ⋮ Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem ⋮ Improved approximation algorithms for directed Steiner forest ⋮ Unnamed Item ⋮ Locating service and charging stations ⋮ Unnamed Item ⋮ The relation of connected set cover and group Steiner tree ⋮ Combination algorithms for Steiner tree variants ⋮ A PTAS for the Steiner Forest Problem in Doubling Metrics ⋮ Complexity of minimum corridor guarding problems ⋮ Adaptive Submodular Ranking and Routing ⋮ Watchman routes for lines and line segments ⋮ A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics ⋮ The minimum vulnerability problem ⋮ On the hardness of full Steiner tree problems ⋮ Approximating \(k\)-generalized connectivity via collapsing HSTs ⋮ A polylogarithmic approximation algorithm for 2-edge-connected dominating set ⋮ The Bursty Steiner Tree Problem ⋮ Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems ⋮ Local search algorithm for universal facility location problem with linear penalties ⋮ GENERALIZED WATCHMAN ROUTE PROBLEM WITH DISCRETE VIEW COST ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ THE MINIMUM GUARDING TREE PROBLEM ⋮ A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem ⋮ Hedging uncertainty: approximation algorithms for stochastic optimization problems ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ Some formulations for the group Steiner tree problem ⋮ Exact and approximate equilibria for optimal group network formation ⋮ Approximation algorithms for group prize-collecting and location-routing problems ⋮ Generalized network design problems. ⋮ Balls and Funnels: Energy Efficient Group-to-Group Anycasts ⋮ Network-Design with Degree Constraints ⋮ APPROXIMATION ALGORITHMS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM WITH DISCRETE AND CONTINUOUS NEIGHBORHOODS ⋮ The minimum degree group Steiner problem ⋮ On approximation algorithms for the terminal Steiner tree problem ⋮ Approximating fault-tolerant group-Steiner problems ⋮ Unnamed Item ⋮ Efficient Black-Box Reductions for Separable Cost Sharing ⋮ The polymatroid Steiner problems ⋮ A greedy approximation algorithm for the group Steiner problem ⋮ On full Steiner trees in unit disk graphs ⋮ On approximating planar metrics by tree metrics. ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ On fixed cost \(k\)-flow problems ⋮ 2-node-connectivity network design
This page was built for publication: A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
