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

DOI10.1002/NET.3230190705zbMATH Open0682.90090OpenAlexW2115981193MaRDI QIDQ4732318FDOQ4732318

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

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

zbMATH Keywords

relaxation boundSteiner tree problem in networks

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• 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)