The node-weighted Steiner tree problem. (English) Zbl 0645.90092
Summary: The general node-weighted Steiner triple tree problem is an extension of the standard Steiner tree problem by the addition of node-associated weights. This article analyzes a special case of that problem, where the set of nodes, which must be included in the solution tree, consists of a single node, and all node weights are negative. The special case is shown to be NP-complete, its integer programming formulation is presented, and heuristic procedures are proposed. Using Lagrangian relaxation and subgradient optimization, tight lower bounds were derived and utilized by a branch and bound algorithm. The effectiveness of the developed procedures is demonstrated by a set of computational experiments.
MSC:
| 90C35 | Programming involving graphs or networks |
| 68Q25 | Analysis of algorithms and problem complexity |
| 90C10 | Integer programming |
| 90C27 | Combinatorial optimization |
| 05C05 | Trees |
Keywords:
node-weighted Steiner triple tree problem; node-associated weights; NP- complete; heuristic procedures; Lagrangian relaxation; subgradient optimization; tight lower bounds; branch and boundReferences:
| [1] | Aneja, Networks 10 pp 167– (1980) |
| [2] | Beasley, Networks 14 pp 147– (1984) |
| [3] | Corneujols, Management Sci. 23 pp 789– (1977) |
| [4] | Dreyfus, Networks 1 pp 195– (1972) |
| [5] | Erlenkotter, Operations Res. 26 pp 992– (1978) |
| [6] | Fisher, Management Sci. 27 pp 1– (1981) |
| [7] | and , Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, San Francisco (1979). · Zbl 0411.68039 |
| [8] | and , Optimal solution methods for large scale multiple traveling salesman problems. Working Paper, The Graduate School of Management, The University of Rochester, Rochester, New York (1980). |
| [9] | Gavish, Networks 12 pp 355– (1982) |
| [10] | Geoffrion, Mathe. Programming Study 2 pp 82– (1974) · Zbl 0395.90056 · doi:10.1007/BFb0120690 |
| [11] | Geoffrion, Management Sci. 20 pp 822– (1974) |
| [12] | Geoffrion, AIIE Trans. 10 pp 40– (1978) · doi:10.1080/05695557808975181 |
| [13] | Hakimi, Networks 1 pp 113– (1971) |
| [14] | Held, Operations Res. 18 pp 1138– (1970) |
| [15] | and , Location on networks: theory and algorithms. MIT, Cambridge, MA (1979). |
| [16] | and , Fundamentals of Computer Algorithms, Computer Science Press, Inc., Potomac, MD (1978). · Zbl 0442.68022 |
| [17] | Mirzaian, Networks 15 pp 1– (1985) |
| [18] | Shortest connection networks and some generalizations, Bell Syst. Tech. Jo. (1957) 1389–1401. |
| [19] | Subgradient optimization. In , , and (eds.), Combinatorial Optimization. Wiley, New York (1979). · Zbl 0401.00019 |
| [20] | Optimizing 2-way joins in fragmented databases systems. Working Paper No. MS-2, School of Business Administration, University of California, Berkeley (1983). |
| [21] | Shore, Networks 12 pp 323– (1982) |
| [22] | Spira, SIAM Jo. Comput. 4 pp 375– (1975) |
| [23] | A dual ascent approach for Steiner tree problems on a directed graph. Report OR&S-82–3, Department of Mathematical Sciences and Curriculum on OR&S Rensselaer Polytechnic Institute, Troy, NY 1982. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
