Parameterized Approximations for the Minimum Diameter Vertex-Weighted Steiner Tree Problem in Graphs with Parameterized Weights
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
Let [Formula: see text] be a weighted undirected connected graph, where [Formula: see text] is the set of vertices, [Formula: see text] is the set of edges, [Formula: see text] is a subset of terminals, [Formula: see text] denotes the weight associated with edge [Formula: see text], and [Formula: see text] denotes the weight associated with vertex [Formula: see text]. Let [Formula: see text] be a Steiner tree in [Formula: see text] to interconnect all terminals in [Formula: see text]. For any two terminals, [Formula: see text], we consider the weighted tree distance on [Formula: see text] from [Formula: see text] to [Formula: see text], defined as the weight of [Formula: see text] times the classic tree distance on [Formula: see text] from [Formula: see text] to [Formula: see text]. The longest weighted tree distance on [Formula: see text] between terminals is named the weighted diameter of [Formula: see text]. The Minimum Diameter Vertex-Weighted Steiner Tree Problem (MDWSTP) asks for a Steiner tree in [Formula: see text] of the minimum weighted diameter to interconnect all terminals in [Formula: see text]. In this paper, we introduce two classes of parameterized graphs (PG), [Formula: see text]-PG and [Formula: see text]-PG, in terms of the parameterized upper bound on the ratio of two vertex weights, and a weaker version of the parameterized triangle inequality, respectively, and present approximation algorithms of a parameterized factor for the MDWSTP in them. For the MDWSTP in an edge-weighted [Formula: see text]-PG, we present an approximation algorithm of a parameterized factor [Formula: see text]. For the MDWSTP in a vertex-weighted [Formula: see text]-PG, we first present a simple approximation algorithm of a parameterized factor [Formula: see text], where [Formula: see text] is tight when [Formula: see text], and further develop another approximation algorithm of a slightly improved factor.
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.002 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.001 | 0.001 |
| 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.001 |
| 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