✦ LIBER ✦

Hypergraphic LP Relaxations for Steiner Trees

✍ Scribed by Chakrabarty, Deeparnab; Könemann, Jochen; Pritchard, David

Book ID: 126047086
Publisher: Society for Industrial and Applied Mathematics
Year: 2013
Tongue: English
Weight: 418 KB
Volume: 27
Category: Article
ISSN: 0895-4801
DOI: 10.1137/110845793

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Steiner minimal trees in Lp2

✍ Dietmar Cieslik; Johann Linhart 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 463 KB

For a finite set of points in a metric space a Steiner Minimal Tree (SMT) is a shortest tree which interconnects these points. We also consider a relative of this problem allowing at most k additional points in the tree (k-SMT), where k is a given number. We intend to discuss these problems for all

A partition-based relaxation for Steiner

A partition-based relaxation for Steiner trees

✍ Jochen Könemann; David Pritchard; Kunlun Tan 📂 Article 📅 2009 🏛 Springer-Verlag 🌐 English ⚖ 407 KB

Integrality gap of the hypergraphic rela

Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound

✍ Deeparnab Chakrabarty; Jochen Könemann; David Pritchard 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 281 KB

Integrality Ratio for Group Steiner Tree

Integrality Ratio for Group Steiner Trees and Directed Steiner Trees

✍ Halperin, Eran; Kortsarz, Guy; Krauthgamer, Robert; Srinivasan, Aravind; Wang, N 📂 Article 📅 2007 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 242 KB

Probabilistic analysis of an lp relaxati

Probabilistic analysis of an lp relaxation bound for the steiner problem in networks

✍ Anjani Jain 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 395 KB

Algorithms for terminal Steiner trees

✍ Fábio Viduani Martinez; José Coelho de Pina; José Soares 📂 Article 📅 2007 🏛 Elsevier Science 🌐 English ⚖ 499 KB