𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Reduction tests for the prize-collecting Steiner problem

✍ Scribed by Eduardo Uchoa

Publisher
Elsevier Science
Year
2006
Tongue
English
Weight
190 KB
Volume
34
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Variations of the prize-collecting Stein
Variations of the prize-collecting Steiner tree problem
✍ Olena Chapovska; Abraham P. Punnen πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 136 KB

## Abstract The prize‐collecting Steiner tree problem is well known to be NP‐hard. We consider seven variations of this problem generalizing several well‐studied bottleneck and minsum problems with feasible solutions as trees of a graph. Four of these problems are shown to be solvable in __O__(__m_

Strong lower bounds for the prize collec
Strong lower bounds for the prize collecting Steiner problem in graphs
✍ Abilio Lucena; Mauricio G.C Resende πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 260 KB

In this paper, we present an integer programming formulation of the prize collecting Steiner problem in graphs (PCSPG) and describe an algorithm to obtain lower bounds for the problem. The algorithm is based on polyhedral cutting planes and is initiated with tests that attempt to reduce the size of