On Rajagopalan and Vazirani's 32e-approximation bound for the iterated 1-Steiner heuristic

DOI10.1016/S0020-0190(03)00210-2MaRDI QIDQ1007642zbMATH OpenDBLPWikidataFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1445376
• Tighter Bounds for Graph Steiner Tree Approximation
• A partition-based relaxation for Steiner trees
• scientific article; zbMATH DE number 1305435
• A faster approximation algorithm for the Steiner problem in graphs

Cited in

(3)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1007642)