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

DOI10.1002/NET.3230190705MaRDI QIDQ4732318zbMATH OpenOpenAlexFDO

Authors Anjani Jain

Publication date 1989

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.3230190705

zbMATH Keywords

relaxation boundSteiner tree problem in networks

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35) Trees (05C05)

Recommendations

• A comparison of Steiner tree relaxations
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• An improved LP-based approximation for Steiner tree
• LP Rounding Approximation Algorithms for Stochastic Network Design
• Steiner tree approximation via iterative randomized rounding

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• Send-and-Split Method for Minimum-Concave-Cost Network Flows

Cited in

(6)

• Comments on Bern's probabilistic results on rectilinear Steiner trees
• An integer programming formulation of the Steiner problem in graphs
• Continuous approximation formulas for location problems
• A primal-dual approximation algorithm for the Steiner forest problem
• Probabilistic Analysis of a Relaxation for the k-Median Problem
• A probabilistic analysis of the maximal covering location problem

This page was built for publication: Probabilistic analysis of an lp relaxation bound for the steiner problem in networks

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