New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem

DOI10.1007/978-3-540-68891-4_24MaRDI QIDQ3503858zbMATH OpenOpenAlexFDO

Authors Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani

Publication date 10 June 2008

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-68891-4_24

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• New geometry-inspired relaxations and algorithms for the metric Steiner tree problem
• Matroids and integrality gaps for hypergraphic Steiner tree relaxations
• scientific article; zbMATH DE number 1305468
• On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree
• Recent results on approximating the Steiner tree problem and its generalizations

Cited in

(8)

• Approximation of Steiner forest via the bidirected cut relaxation
• Approaches to the Steiner Problem in Networks
• scientific article; zbMATH DE number 1305468 (Why is no real title available?)
• scientific article; zbMATH DE number 1182759 (Why is no real title available?)
• A partition-based relaxation for Steiner trees
• New geometry-inspired relaxations and algorithms for the metric Steiner tree problem
• An improved approximation guarantee for prize-collecting TSP
• A critical review of discrete filled function methods in solving nonlinear discrete optimization problems

This page was built for publication: New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem

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