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é
Das Steinerbaumproblem in Graphen (STP) ist ein NP-schweres kombinatorisches Optimierungsproblem, welches sowohl aus theoretischer als auch aus praktischer Sicht relevant ist. Die Anwendungsfälle reichen vom VLSI-Design bis hin zum Lösen 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 möglich eine optimale Lösung zu finden. Problematisch sind vor allem große Instanzen, die in praktischen Anwendungen relativ häufig auftreten. In solchen Fällen bleibt oft nur die Verwendung von heuristischen Methoden. Diese sind auf die Berechnung von guten, jedoch suboptimalen Lösungen in relativ kurzer Zeit spezialisiert. In dieser Diplomarbeit wird eine neue Konstruktionsheuristik vorgestellt, die Partitionierungsmethoden nutzt, um speziell mit großen Probleminstanzen umgehen zu können. Hierzu wird eine Instanz systematisch in kleinere Instanzen zerlegt, die einfach genug sind, um sie mit einem exakten Algorithmus optimal zu lösen. Danach wird eine heuristische Lösung der ursprünglichen Instanz durch Zusammensetzen der Teillösungen erzeugt. Zur Realisierung dieses Verfahrens werden sowohl exakte und heuristische Lösungsmethoden für das STP als auch Algorithmen zur Partitionierung von Graphen kombiniert. Für die Berechnung von exakten Lösungen wird ein Branch-and-Cut Verfahren verwendet. Das zugrundeliegende ILP-Model basiert auf den bekannten directed-cut-constraints, führt jedoch zusätzlich noch die Verwendung von Knotenvariablen ein. Der zugehörigen Separierungsmethode liegen verschiedene Verbesserungen aus der Literatur zugrunde. Zur Partitionierung wird das METIS Graph Partitioning Framework verwendet. Außerdem wird ein einfacher Greedy-Algorithmus vorgestellt, welcher eine Instanz durch die Kombination mehrerer Regionen in einem Voronoi-Diagram erstellt. Die implementierten Algorithmen werden zusätzlich in einen memetischen Algorithmus integriert, darunter die vorgestellte Konstruktionsheuristik, Reduktionstests, ein Algorithmus zur Rekombination von Lösungen und Variable Neighorhood Descent. Die verwendeten Nachbarschaftsstrukturen basieren auf Steiner node insertion, Steiner node elimination, key-node elimination und key-path exchange. Alle Algorithmen werden experimentell evaluiert. Die Testinstanzen dafür stammen aus der SteinLib, welche eine Sammlung von Benchmark-Instanzen für das STP darstellt, und aus einer Gruppe aus neuen Instanzen, die Netzwerkdesignprobleme aus der Praxis beschreiben. Die Ergebnisse zeigen, dass Lösungsqualität und Laufzeit des vorgestellten Verfahrens auch für große Instanzen akzeptabel sind.
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,000 |
| Études des sciences et des technologies | 0,000 | 0,000 |
| Communication savante | 0,000 | 0,000 |
| Science ouverte | 0,000 | 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