A new partition-based heuristic for the Steiner tree problem in large graphs
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
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.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.000 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.000 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it