Log in

Relevant bibliographies by topics / Prize Collecting Steiner Tree Problem

Contents

Journal articles
Dissertations / Theses
Book chapters
Conference papers

Academic literature on the topic 'Prize Collecting Steiner Tree Problem'

Author: Grafiati

Published: 5 June 2025

Last updated: 15 July 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Prize Collecting Steiner Tree Problem.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Prize Collecting Steiner Tree Problem"

1

Chapovska, Olena, and Abraham P. Punnen. "Variations of the prize-collecting Steiner tree problem." Networks 47, no. 4 (2006): 199–205. http://dx.doi.org/10.1002/net.20106.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Goldbarg, Elizabeth Ferreira Gouvêa, Marco Goldbarg, and Cristine Schmidt. "A Hybrid Transgenetic Algorithm for the Prize Collecting Steiner Tree Problem." JUCS - Journal of Universal Computer Science 14, no. (15) (2008): 2491–511. https://doi.org/10.3217/jucs-014-15-2491.

Full text

Abstract:

Evolutionary algorithms are effective search tools for tackling difficult optimization problems. In this paper an algorithm based on living processes where cooperation is the main evolutionary strategy is applied to the Prize Collecting Steiner Tree Problem, an NP-hard combinatorial optimization problem. The Transgenetic Algorithm presented here is hybridized with path-relinking. Computational results of an experiment performed with benchmark instances are reported. The results obtained for the Prize Collecting Steiner Tree Problem with the application of the hybrid Transgenetic Algorithm are compared with the results of three effective approaches presented previously. The computational experiment shows that the proposed approach is very competitive concerning both quality of solution and processing time.

APA, Harvard, Vancouver, ISO, and other styles

3

Han, Lu, Changjun Wang, Dachuan Xu, and Dongmei Zhang. "Algorithms for the Prize-Collecting $k$-Steiner Tree Problem." Tsinghua Science and Technology 27, no. 5 (2022): 785–92. http://dx.doi.org/10.26599/tst.2021.9010053.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Haouari, Mohamed, Safa Bhar Layeb, and Hanif D. Sherali. "Algorithmic expedients for the Prize Collecting Steiner Tree Problem." Discrete Optimization 7, no. 1-2 (2010): 32–47. http://dx.doi.org/10.1016/j.disopt.2010.01.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Rehfeldt, Daniel, and Thorsten Koch. "On the Exact Solution of Prize-Collecting Steiner Tree Problems." INFORMS Journal on Computing 34, no. 2 (2022): 872–89. http://dx.doi.org/10.1287/ijoc.2021.1087.

Full text

Abstract:

The prize-collecting Steiner tree problem (PCSTP) is a well-known generalization of the classic Steiner tree problem in graphs, with a large number of practical applications. It attracted particular interest during the 11th DIMACS Challenge in 2014, and since then, several PCSTP solvers have been introduced in the literature. Although these new solvers further, and often drastically, improved on the results of the DIMACS Challenge, many PCSTP benchmark instances have remained unsolved. The following article describes further advances in the state of the art in exact PCSTP solving. It introduces new techniques and algorithms for PCSTP, involving various new transformations (or reductions) of PCSTP instances to equivalent problems, for example, to decrease the problem size or to obtain a better integer programming formulation. Several of the new techniques and algorithms provably dominate previous approaches. Further theoretical properties of the new components, such as their complexity, are discussed. Also, new complexity results for the exact solution of PCSTP and related problems are described, which form the base of the algorithm design. Finally, the new developments also translate into a strong computational performance: the resulting exact PCSTP solver outperforms all previous approaches, both in terms of runtime and solvability. In particular, it solves several formerly intractable benchmark instances from the 11th DIMACS Challenge to optimality. Moreover, several recently introduced large-scale instances with up to 10 million edges, previously considered to be too large for any exact approach, can now be solved to optimality in less than two hours. Summary of Contribution: The prize-collecting Steiner tree problem (PCSTP) is a well-known generalization of the classic Steiner tree problem in graphs, with many practical applications. The article introduces and analyses new techniques and algorithms for PCSTP that ultimately aim for improved (practical) exact solution. The algorithmic developments are underpinned by results on theoretical aspects, such as fixed-parameter tractability of PCSTP. Computationally, we considerably push the limits of tractibility, being able to solve PCSTP instances with up to 10 million edges. The new solver, which also considerably outperforms the state of the art on smaller instances, will be made publicly available as part of the SCIP Optimization Suite.

APA, Harvard, Vancouver, ISO, and other styles

6

Feofiloff, Paulo, Cristina G. Fernandes, Carlos E. Ferreira, and José Coelho de Pina. "Primal-dual approximation algorithms for the Prize-Collecting Steiner Tree Problem." Information Processing Letters 103, no. 5 (2007): 195–202. http://dx.doi.org/10.1016/j.ipl.2007.03.012.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Gutner, Shai. "Elementary approximation algorithms for prize collecting Steiner tree problems." Information Processing Letters 107, no. 1 (2008): 39–44. http://dx.doi.org/10.1016/j.ipl.2007.12.010.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Han, Lu, Dachuan Xu, Donglei Du, and Chenchen Wu. "A 5-approximation algorithm for the k-prize-collecting Steiner tree problem." Optimization Letters 13, no. 3 (2017): 573–85. http://dx.doi.org/10.1007/s11590-017-1135-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Haouari, Mohamed, Safa Bhar Layeb, and Hanif D. Sherali. "The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches." Computational Optimization and Applications 40, no. 1 (2007): 13–39. http://dx.doi.org/10.1007/s10589-007-9072-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Haouari, Mohamed, and Jouhaina Chaouachi Siala. "A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem." Computers & Operations Research 33, no. 5 (2006): 1274–88. http://dx.doi.org/10.1016/j.cor.2004.09.017.

Full text

APA, Harvard, Vancouver, ISO, and other styles

More sources

Dissertations / Theses on the topic "Prize Collecting Steiner Tree Problem"

1

Minkoff, Maria 1976. "The Prize Collecting Steiner Tree problem." Thesis, Massachusetts Institute of Technology, 2000. http://hdl.handle.net/1721.1/86544.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Matsubara, Camila Mari. "Algoritmos para o problema da árvore de Steiner com coleta de prêmios." Universidade de São Paulo, 2012. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-18082014-170526/.

Full text

Abstract:

Neste projeto estudamos algoritmos de aproximação para o problema da árvore de Steiner com coleta de prêmios. Trata-se de uma generalização do problema da árvore de Steiner, onde é dado um grafo com custos positivos nas arestas e penalidades positivas nos vértices. O objetivo é encontrar uma subárvore do grafo que minimize a soma dos custos das arestas mais a soma das penalidades dos vértices que não pertencem à subárvore. Em 2009, os autores Archer, Bateni, Hajiaghayi e Karloff obtiveram pela primeira vez um algoritmo com fator de aproximação estritamente menor do que 2. Além de analisarmos este algoritmo, estudamos também a implementação de algoritmos 2-aproximação para o problema da árvore de Steiner e da árvore de Steiner com coleta de prêmios.<br>In this project we analyze approximation algorithms for the prize-collecting Steiner tree problem. This is a generalization of the Steiner tree problem, in which it is given a graph with positive costs in edges and positive penalties in vertices. The goal is to find a subtree of the graph that minimizes the sum of costs of edges plus the sum of the penalties of the vertices that don\'t belong to the subtree. In 2009, the authors Archer, Bateni, Hajiaghayi e Karloff described, for the first time an algorithm with approximation factor strictly less than 2. Besides analyzing this algorithm, we also study the implementation of 2-approximation algorithms to the Steiner tree problem and prize-collecting Steiner tree problem.

APA, Harvard, Vancouver, ISO, and other styles

3

Rossin, Samuel. "Steiner Tree Games." Oberlin College Honors Theses / OhioLINK, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=oberlin1464700445.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Li, Bi. "Décompositions arborescentes et problèmes de routage." Thesis, Nice, 2014. http://www.theses.fr/2014NICE4088/document.

Full text

Abstract:

Dans cette thèse, nous étudions les décompositions arborescentes qui satisfont certaines contraintes supplémentaires et nous proposons des algorithmes pour les calculer dans certaines classes de graphes. Finalement, nous résolvons des problèmes liés au routage en utilisant ces décompositions ainsi que des propriétés structurelles des graphes. Cette thèse est divisée en deux parties. Dans la première partie, nous étudions les décompositions arborescentes satisfaisant des propriétés spécifiques. Dans le Chapitre 2, nous étudions les décompositions de taille minimum, c’est-À-Dire avec un nombre minimum de sacs. Etant donné une entier k 4 fixé, nous prouvons que le problème de calculer une décomposition arborescente de largeur au plus k et de taille minimum est NP-Complet dans les graphes de largeur arborescente au plus 4. Nous décrivons ensuite des algorithmes qui calculent des décompositions de taille minimum dans certaines classes de graphes de largeur arborescente au plus 3. Ces résultats ont été présentés au workshop international ICGT 2014. Dans le Chapitre 3, nous étudions la cordalité des graphes et nous introduisons la notion de k-Good décomposition arborescente. Nous étudions tout d’abord les jeux de Gendarmes et Voleur dans les graphes sans long cycle induit. Notre résultat principal est un algorithme polynomial qui, étant donné un graphe G, soit trouve un cycle induit de longueur au moins k+1, ou calcule une k-Good décomposition de G. Ces résultats ont été publiés à la conférence internationale ICALP’12 et dans la revue internationale Algorithmica. Dans la seconde partie de la thèse, nous nous concentrons sur des problèmes de routage<br>A tree decomposition of a graph is a way to represent it as a tree by preserving some connectivity properties of the initial graph. Tree decompositions have been widely studied for their algorithmic applications, in particular using dynamic programming approach. In this thesis, we study tree decompositions satisfying various constraints and design algorithms to compute them in some graph classes. We then use tree decompositions or specific graph properties to solve several problems related to routing. The thesis is divided into two parts. In the first part, we study tree decompositions satisfying some properties. In Chapter 2, we investigate minimum size tree decompositions, i.e., with minimum number of bags. Given a fixed k 4, we prove it is NP-Hard to compute a minimum size decomposition with width at most k in the class of graphs with treewidth at least 4. We design polynomial time algorithms to compute minimum size tree decompositions in some classes of graphs with treewidth at most 3 (including trees). Part of these results will be presented in ICGT 2014. In Chapter 3, we study the chordality (longest induced cycle) of graphs and introduce the notion of good tree decomposition (where each bag must satisfy some particular structure). Precisely, we study the Cops and Robber games in graphs with no long induced cycles. Our main result is the design of a polynomial-Time algorithm that either returns an induced cycle of length at least k+1 of a graph G or compute a k-Good tree decomposition of G. These results have been published in ICALP 2012 and Algorithmica. In the second part of the thesis, we focus on routing problems

APA, Harvard, Vancouver, ISO, and other styles

5

Sadeghian, Sadeghabad Sina. "Node-Weighted Prize Collecting Steiner Tree and Applications." Thesis, 2013. http://hdl.handle.net/10012/7557.

Full text

Abstract:

The Steiner Tree problem has appeared in the Karp's list of the first 21 NP-hard problems and is well known as one of the most fundamental problems in Network Design area. We study the Node-Weighted version of the Prize Collecting Steiner Tree problem. In this problem, we are given a simple graph with a cost and penalty value associated with each node. Our goal is to find a subtree T of the graph minimizing the cost of the nodes in T plus penalty of the nodes not in T. By a reduction from set cover problem it can be easily shown that the problem cannot be approximated in polynomial time within factor of (1-o(1))ln n unless NP has quasi-polynomial time algorithms, where n is the number of vertices of the graph. Moss and Rabani claimed an O(log n)-approximation algorithm for the problem using a Primal-Dual approach in their STOC'01 paper \cite{moss2001}. We show that their algorithm is incorrect by providing a counter example in which there is an O(n) gap between the dual solution constructed by their algorithm and the optimal solution. Further, evidence is given that their algorithm probably does not have a simple fix. We propose a new algorithm which is more involved and introduces novel ideas in primal dual approach for network design problems. Also, our algorithm is a Lagrangian Multiplier Preserving algorithm and we show how this property can be utilized to design an O(log n)-approximation algorithm for the Node-Weighted Quota Steiner Tree problem using the Lagrangian Relaxation method. We also show an application of the Node Weighted Quota Steiner Tree problem in designing algorithm with better approximation factor for Technology Diffusion problem, a problem proposed by Goldberg and Liu in \cite{goldberg2012} (SODA 2013). In Technology Diffusion, we are given a graph G and a threshold θ(v) associated with each vertex v and we are seeking a set of initial nodes called the seed set. Technology Diffusion is a dynamic process defined over time in which each vertex is either active or inactive. The vertices in the seed set are initially activated and each other vertex v gets activated whenever there are at least θ(v) active nodes connected to v through other active nodes. The Technology Diffusion problem asks to find the minimum seed set activating all nodes. Goldberg and Liu gave an O(rllog n)-approximation algorithm for the problem where r and l are the diameter of G and the number of distinct threshold values, respectively. We improve the approximation factor to O(min{r,l}log n) by establishing a close connection between the problem and the Node Weighted Quota Steiner Tree problem.

APA, Harvard, Vancouver, ISO, and other styles

6

Rahmah, Dini Nuzulia, and 林娣美. "Object Tracking via Structured Output Support Vector Machine and Prize-Collecting Steiner Tree." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/cj8qbx.

Full text

Abstract:

碩士<br>國立臺灣科技大學<br>資訊工程系<br>102<br>Object tracking in video is a challenging problem in various applications, such as video editing, video surveillance, video compression, video retrieval, and etc. Tracking object is in general not trivial due to loss of information caused by frequent occlusions, similar target appearances, missed detection, inaccurate responses and illumination change. In this thesis, we present a novel object video tracking algorithm via structured output prediction classifier integrated with Prize-Collecting Steiner Tree (PCST). Given an initial bounding box with its position, we first divide it into sub-blocks with a predefined size. And then we extract the features from each sub-blocks with a structured output prediction classifier. We treat the sub-blocks obtained from the initial bounding box as positive samples and then randomly choose negative samples from search windows defined by the specific area around the bounding box. We obtain prediction scores for each sub-blocks both from positive and negative samples. After that, we construct a region-graph with sub-blocks as nodes and classifier's score as weight to detect the target object in each frame. We then employ PCST to obtain the optimal solution for tracking the object in the consecutive video. Our experimental results show that the proposed method outperforms several state-of-the-art object tracking algorithms.

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Prize Collecting Steiner Tree Problem"

1

Han, Lu, Changjun Wang, Dachuan Xu, and Dongmei Zhang. "The Prize-Collecting k-Steiner Tree Problem." In Parallel and Distributed Computing, Applications and Technologies. Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-69244-5_33.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Klau, Gunnar W., Ivana Ljubić, Petra Mutzel, Ulrich Pferschy, and René Weiskircher. "The Fractional Prize-Collecting Steiner Tree Problem on Trees." In Algorithms - ESA 2003. Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/978-3-540-39658-1_62.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Pedersen, Jaap, and Ivana Ljubić. "Prize-Collecting Steiner Tree Problem and Its Variants." In Encyclopedia of Optimization. Springer International Publishing, 2024. http://dx.doi.org/10.1007/978-3-030-54621-2_869-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Sun, Jian, Haiyun Sheng, Yuefang Sun, and Xiaoyan Zhang. "Approximation Algorithm for Stochastic Prize-Collecting Steiner Tree Problem." In Algorithmic Aspects in Information and Management. Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-27195-4_24.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Pedrosa, Lehilton L. C., and Hugo K. K. Rosado. "A 2-Approximation for the k-Prize-Collecting Steiner Tree Problem." In LATIN 2020: Theoretical Informatics. Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-61792-9_7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Ming, Yi-Fei, Si-Bo Chen, Yong-Quan Chen, and Zhang-Hua Fu. "A Fast Vertex-Swap Operator for the Prize-Collecting Steiner Tree Problem." In Lecture Notes in Computer Science. Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-93701-4_43.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Álvarez-Miranda, E., A. Candia, X. Chen, X. Hu, and B. Li. "Efficient Algorithms for the Prize Collecting Steiner Tree Problems with Interval Data." In Algorithmic Aspects in Information and Management. Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-14355-7_3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Klau, Gunnar W., Ivana Ljubić, Andreas Moser, et al. "Combining a Memetic Algorithm with Integer Programming to Solve the Prize-Collecting Steiner Tree Problem." In Genetic and Evolutionary Computation – GECCO 2004. Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-24854-5_125.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Akhmedov, Murodzhon, Ivo Kwee, and Roberto Montemanni. "A Comparison of Heuristic Methods for the Prize-Collecting Steiner Tree Problem and Their Application in Genomics." In Operations Research Proceedings. Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-42902-1_14.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Bailly-Bechet, Marc, Alfredo Braunstein, and Riccardo Zecchina. "A Prize-Collecting Steiner Tree Approach for Transduction Network Inference." In Computational Methods in Systems Biology. Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-03845-7_6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Prize Collecting Steiner Tree Problem"

1

Akhmedov, Murodzhon, Ivo Kwee, and Roberto Montemanni. "A matheuristic algorithm for the Prize-collecting Steiner Tree Problem." In 2015 3rd International Conference on Information and Communication Technology (ICoICT ). IEEE, 2015. http://dx.doi.org/10.1109/icoict.2015.7231460.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Hosokawa, Y., and E. Chiba. "A heuristic algorithm for the prize collecting Steiner Tree problem." In 2014 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM). IEEE, 2014. http://dx.doi.org/10.1109/ieem.2014.7058608.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Schmidt, Cristine, Elizabeth F. G. Goldbarg, and Marco C. Goldbarg. "A Hybrid Transgenetic Algorithm for the Prize Collecting Steiner Tree Problem." In Seventh International Conference on Intelligent Systems Design and Applications (ISDA 2007). IEEE, 2007. http://dx.doi.org/10.1109/isda.2007.14.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Schmidt, Cristine, Elizabeth F. G. Goldbarg, and Marco C. Goldbarg. "A Hybrid Transgenetic Algorithm for the Prize Collecting Steiner Tree Problem." In Seventh International Conference on Intelligent Systems Design and Applications (ISDA 2007). IEEE, 2007. http://dx.doi.org/10.1109/isda.2007.4389620.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Rojas, Francisco, and Federico Meza. "A Parallel Distributed Genetic Algorithm for the Prize Collecting Steiner Tree Problem." In 2015 International Conference on Computational Science and Computational Intelligence (CSCI). IEEE, 2015. http://dx.doi.org/10.1109/csci.2015.67.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Hajiaghayi, Mohammad Taghi, and Kamal Jain. "The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema." In the seventeenth annual ACM-SIAM symposium. ACM Press, 2006. http://dx.doi.org/10.1145/1109557.1109626.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Ahmadi, Ali, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, and Mohammad Mahdavi. "Prize-Collecting Steiner Tree: A 1.79 Approximation." In STOC '24: 56th Annual ACM Symposium on Theory of Computing. ACM, 2024. http://dx.doi.org/10.1145/3618260.3649789.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Archer, Aaron, Mohammad Hossein Bateni, Mohammad Taghi Hajiaghayi, and Howard Karloff. "Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP." In 2009 IEEE 50th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2009. http://dx.doi.org/10.1109/focs.2009.39.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Bateni, MohammadHossein, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx. "A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting." In STOC '16: Symposium on Theory of Computing. ACM, 2016. http://dx.doi.org/10.1145/2897518.2897549.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Konemann, Jochen, Sina Sadeghian, and Laura Sanita. "An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree." In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2013. http://dx.doi.org/10.1109/focs.2013.67.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!