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
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
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.001 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.001 |
| Open science | 0.001 | 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