Parameterized Approximations for the Minimum Diameter Vertex-Weighted Steiner Tree Problem in Graphs with Parameterized Weights
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.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.014 |
| Meta-epidemiology (narrow) | 0.003 | 0.001 |
| Meta-epidemiology (broad) | 0.002 | 0.002 |
| Bibliometrics | 0.001 | 0.003 |
| Science and technology studies | 0.001 | 0.001 |
| Scholarly communication | 0.003 | 0.007 |
| Open science | 0.004 | 0.003 |
| Research integrity | 0.002 | 0.003 |
| Insufficient payload (model declined to judge) | 0.009 | 0.001 |
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 itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".