Premium
Probabilistic analysis of an lp relaxation bound for the steiner problem in networks
Author(s) -
Jain Anjani
Publication year - 1989
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230190705
Subject(s) - linear programming relaxation , steiner tree problem , linear programming , relaxation (psychology) , integer programming , mathematics , probabilistic logic , upper and lower bounds , combinatorics , tree (set theory) , branch and bound , mathematical optimization , discrete mathematics , statistics , psychology , social psychology , mathematical analysis
We investigate probabilistically the relative tightness of a linear programming relaxation bound for an integer programming formulation of the Steiner tree problem in networks. Under two different random modesl of the network, we show that the aggregate linear programming relaxation provides a rapidly diverging bound for the optimal Steiner tree and characterize the rates of divergence.