Buchumschlag

Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Veldt, Nate, Stanley, Thomas, Priest, Benjamin W., Steil, Trevor, Iwabuchi, Keita, Jayram, T. S., Li, Grace J., Sanders, Geoffrey
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Data Structures and Algorithms Machine Learning
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
von: Veldt, Nate, et al.
Veröffentlicht: (2025)

A Simple and Fast $(3+\varepsilon)$-approximation for Constrained Correlation Clustering
von: Veldt, Nate
Veröffentlicht: (2025)

An Improved Combinatorial Algorithm for Edge-Colored Clustering in Hypergraphs
von: Han, Seongjune, et al.
Veröffentlicht: (2026)

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
von: Crane, Alex, et al.
Veröffentlicht: (2025)

On the tractability and approximability of non-submodular cardinality-based $s$-$t$ cut problems in hypergraphs
von: Bengali, Vedangi, et al.
Veröffentlicht: (2024)

Overlapping and Robust Edge-Colored Clustering in Hypergraphs
von: Crane, Alex, et al.
Veröffentlicht: (2023)

Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better
von: Balmaseda, Vicente, et al.
Veröffentlicht: (2024)

The Densest SWAMP problem: subhypergraphs with arbitrary monotonic partial edge rewards
von: Bengali, Vedangi, et al.
Veröffentlicht: (2025)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
von: Adriaens, Florian, et al.
Veröffentlicht: (2024)

Spanning and Metric Tree Covers Parameterized by Treewidth
von: Elkin, Michael, et al.
Veröffentlicht: (2025)

Parallel PLL on DAGs
von: Steil, Patrick
Veröffentlicht: (2025)

Optimal FIFO grouping in public transit networks
von: Steil, Patrick
Veröffentlicht: (2023)

Densest Subhypergraph: Negative Supermodular Functions and Strongly Localized Methods
von: Huang, Yufan, et al.
Veröffentlicht: (2023)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
von: Azarmehr, Amir, et al.
Veröffentlicht: (2024)

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
von: Peng, Pan, et al.
Veröffentlicht: (2026)

Parameterized Algorithms for Spanning Tree Isomorphism by Redundant Set Size
von: Shen, Fangjian, et al.
Veröffentlicht: (2025)

Steiner Forest: A Simplified Better-Than-2 Approximation
von: Gupta, Anupam, et al.
Veröffentlicht: (2025)

New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications
von: Ding, Xiangyun, et al.
Veröffentlicht: (2025)

Sublinear Metric Steiner Forest via Maximal Independent Set
von: Mahabadi, Sepideh, et al.
Veröffentlicht: (2025)

Engineering Weighted Connectivity Augmentation Algorithms
von: Faraj, Marcelo Fonseca, et al.
Veröffentlicht: (2024)

Above-Guarantee Algorithm for Properly Colored Spanning Trees
von: Bai, Yuhang, et al.
Veröffentlicht: (2026)

3/2-Approximation for the Forest Augmentation Problem
von: Çivril, Ali
Veröffentlicht: (2024)

Streaming Algorithms for Geometric Steiner Forest
von: Czumaj, Artur, et al.
Veröffentlicht: (2020)

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
von: Norose, Ryoma, et al.
Veröffentlicht: (2024)

A Better-Than-2 Approximation for the Directed Tree Augmentation Problem
von: Neuwohner, Meike, et al.
Veröffentlicht: (2025)

An Improved Approximation Algorithm for Metric Triangle Packing
von: Zhao, Jingyang, et al.
Veröffentlicht: (2024)

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
von: Feldmann, Andreas Emil, et al.
Veröffentlicht: (2024)

Streaming Algorithms for Connectivity Augmentation
von: Jin, Ce, et al.
Veröffentlicht: (2024)

Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms
von: Mo, Guanlin, et al.
Veröffentlicht: (2024)

Parameterized Approximation Algorithms for TSP on Non-Metric Graphs
von: Zhao, Jingyang, et al.
Veröffentlicht: (2025)

Approximation Algorithms for Packing Cycles and Paths in Complete Graphs
von: Zhao, Jingyang, et al.
Veröffentlicht: (2023)

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
von: Çivril, Ali
Veröffentlicht: (2023)

Pareto Sums of Pareto Sets: Lower Bounds and Algorithms
von: Funke, Daniel, et al.
Veröffentlicht: (2024)

Approximation Algorithms for Steiner Connectivity Augmentation
von: Hathcock, Daniel, et al.
Veröffentlicht: (2023)

Random Multi-Type Spanning Forests for Synchronization on Sparse Graphs
von: Jaquard, Hugo, et al.
Veröffentlicht: (2024)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

Online Disjoint Spanning Trees and Polymatroid Bases
von: Chandrasekaran, Karthekeyan, et al.
Veröffentlicht: (2025)

Planar Length-Constrained Minimum Spanning Trees
von: Hershkowitz, D Ellis, et al.
Veröffentlicht: (2025)

Spanning tree congestion of proper interval graphs
von: Otachi, Yota
Veröffentlicht: (2026)

Simple Length-Constrained Minimum Spanning Trees
von: Hershkowitz, D Ellis, et al.
Veröffentlicht: (2024)