A new partition-based heuristic for the Steiner tree problem in large graphs
Pourquoi ce travail est dans la base
Une base qui oublie comment elle a trouvé un travail ne peut pas être vérifiée. Voici les voies qui ont admis celui-ci.
Notice bibliographique
Résumé
The Steiner tree problem in graphs (STP) is a fundamental N P-hard combinatorial optimization problem of theoretical and practical interest.Common applications range from VLSI design to problems in computational biology.The STP can be informally described as the problem of connecting a subset of special vertices called terminals in a weighted graph at minimum cost.Due to the problem's complexity the computation of optimal solutions may not always be feasible.This holds true especially for large-scale instances which are quite common in realworld scenarios.In such cases, heuristic methods specialized on finding near-optimal solutions in reasonable amounts of time, are generally the only choice.In this master's thesis we propose a new partition-based heuristic for the efficient construction of approximate solutions to the STP in very large graphs.Our algorithm is based on a partitioning approach in which instances are divided into several subinstances which are small enough to be solved optimally.A heuristic solution of the complete instance can then be constructed through the combination of the subinstances' solutions.To this end we combine state-of-the-art exact and heuristic methods for the STP and general graph partitioning.For the exact solution of subinstances we apply a branch-and-cut procedure.The underlying integer linear programming (ILP) model augments a formulation based on the well-known directed-cut-constraints with node variables.The associated separation procedure includes several improvements from literature.For partitioning we use the METIS graph partitioning framework as well as a greedy partitioning algorithm based on the contraction of Voronoi regions.The implemented algorithms are also embedded into a memetic algorithm, which includes the partition-based construction heuristic, reduction tests, an algorithm for solution recombination and a variable neighborhood descent.We use common neighborhood structures from the STP literature: Steiner node insertion, Steiner node elimination, key-node elimination and key-path exchange.All algorithms are evaluated through practical experiments on the SteinLib, a state-of-theart benchmark set for the STP, and a set of new real-world instances from network design.The results show that our approach yields good quality solutions with reasonable runtime, even for large graphs.iii KurzfassungDas Steinerbaumproblem in Graphen (STP) ist ein N P-schweres kombinatorisches Optimierungsproblem, welches sowohl aus theoretischer als auch aus praktischer Sicht relevant ist.Die Anwendungsflle reichen vom VLSI-Design bis hin zum Lsen von wissenschaftlichen Problemen in der Bioinformatik.Beim STP sollen eine Menge an Basisknoten in einem gewichteten Graphen kostenminimal verbunden werden.Da dieses Problem sehr schwierig ist, ist es nicht immer mglich eine optimale Lsung zu finden.Problematisch sind vor allem groe Instanzen, die in praktischen Anwendungen relativ hufig auftreten.In solchen Fllen bleibt oft nur die Verwendung von heuristischen Methoden
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
Prédiction distillée sur la base complète
Imitation des enseignantsNi prévalence calibrée, ni vérité terrain. Validation humaine à venir. Apprise à partir de 10 348 étiquettes directes de Codex et de 10 348 étiquettes directes de Gemma. Le mode candidate est l'union des têtes enseignantes seuillées; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont ni des étiquettes humaines ni des étiquettes directes de modèles de pointe.
Scores Codex et Gemma par catégorie
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,000 | 0,000 |
| Méta-épidémiologie (sens strict) | 0,000 | 0,000 |
| Méta-épidémiologie (sens large) | 0,000 | 0,000 |
| Bibliométrie | 0,000 | 0,001 |
| Études des sciences et des technologies | 0,000 | 0,000 |
| Communication savante | 0,000 | 0,001 |
| Science ouverte | 0,001 | 0,000 |
| Intégrité de la recherche | 0,000 | 0,000 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,000 | 0,000 |
Scores machine (provisoires)
Les deux têtes enseignantes du modèle étudiant, lues sur ce travail. Un score ordonne la base pour la relecture; il n'affirme jamais une catégorie, et le statut de validation accompagne chaque rangée tel quel.
Scores de référence d'un modèle non mature (critères de maturité non atteints, 7 itérations). Un score ordonne; il n'affirme jamais une catégorie.
score_only:v0-immature-baseline · tel quel depuis la passe de notation : score_only signifie que le nombre peut ordonner les travaux, et qu'aucune étiquette de catégorie n'en découle