{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreicbgspwimluwks462443wog2a4tjzl5yj7buos3qo2od5kf4v7ncq",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mg2qxjcnd242"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.24232v1",
  "publishedAt": "2026-03-02T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Nate Veldt",
    "Thomas Stanley",
    "Benjamin W. Priest",
    "Trevor Steil",
    "Keita Iwabuchi",
    "T. S. Jayram",
    "Grace J. Li",
    "Geoffrey Sanders"
  ],
  "textContent": "**Authors:** Nate Veldt, Thomas Stanley, Benjamin W. Priest, Trevor Steil, Keita Iwabuchi, T. S. Jayram, Grace J. Li, Geoffrey Sanders\n\nWe present improved learning-augmented algorithms for finding an approximate minimum spanning tree (MST) for points in an arbitrary metric space. Our work follows a recent framework called metric forest completion (MFC), where the learned input is a forest that must be given additional edges to form a full spanning tree. Veldt et al. (2025) showed that optimally completing the forest takes $Ω(n^2)$ time, but designed a 2.62-approximation for MFC with subquadratic complexity. The same method is a $(2γ+ 1)$-approximation for the original MST problem, where $γ\\geq 1$ is a quality parameter for the initial forest. We introduce a generalized method that interpolates between this prior algorithm and an optimal $Ω(n^2)$-time MFC algorithm. Our approach considers only edges incident to a growing number of strategically chosen ``representative'' points. One corollary of our analysis is to improve the approximation factor of the previous algorithm from 2.62 for MFC and $(2γ+1)$ for metric MST to 2 and $2γ$ respectively. We prove this is tight for worst-case instances, but we still obtain better instance-specific approximations using our generalized method. We complement our theoretical results with a thorough experimental evaluation.",
  "title": "Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion"
}