The prize collecting Steiner tree problem: theory and practice

By David S. Johnson, Maria Minkoff, Steven J. Phillips. ACM-SIAM Symposium on Discrete Algorithms, 2000

299 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Efficient Informative Sensing using Multiple Robots (2014, background): “For the case of the unrooted OP (when no starting location is specified), the approximation guarantees known for Prize Collecting TSP and k-TSP can be easily extended (Johnson et al., 2000).”
Near-optimal sensor placements: maximizing information while minimizing communication cost (2006, methodology): “Hence, we approximately solve the Quota-MST problem (for the covering version) or the Budget-MST problem (for the maximization problem) on g' [7, 12] (Fig.”
Sharing the Cost of Multicast Transmissions (2001, methodology): “Because computing W( ) is equivalent to the net-worth maximization version of the Prize-Collecting Steiner-Tree problem [15], it is NP-hard.”
Robust Submodular Observation Selection (2008, background): “Kouvelis and Yu (1997) introduce several notions of robust discrete problems, presents hardness results and a class of robust problems that can be optimally solved.”
Approximation algorithms for orienteering and discounted-reward TSP (2003, methodology): “This problem is also called the Budget Prize-Collecting Steiner Tree problem [13].”