On Rajagopalan and Vazirani's \(\frac{3}{2}e\)-approximation bound for the iterated 1-Steiner heuristic

DOI10.1016/S0020-0190(03)00210-2zbMath1173.68868DBLPjournals/ipl/Rizzi03WikidataQ29036224 ScholiaQ29036224MaRDI QIDQ1007642

Romeo Rizzi

Publication date: 23 March 2009

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

local searchapproximation algorithmsSteiner treebit scalingiterated 1-Steiner heuristic

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (3)

New geometry-inspired relaxations and algorithms for the metric Steiner tree problem ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ A partition-based relaxation for Steiner trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On Rajagopalan and Vazirani's \(\frac{3}{2}e\)-approximation bound for the iterated 1-Steiner heuristic