Cover Image

An Approximation Algorithm for Graph Label Selection

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	John, Josia, Meierhans, Simon, Gutenberg, Maximilian Probst
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
by: Meierhans, Simon, et al.
Published: (2025)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
by: Meierhans, Simon, et al.
Published: (2025)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
by: Chen, Daoyuan, et al.
Published: (2024)

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
by: Brand, Jan van den, et al.
Published: (2024)

Near-Optimal Algorithm for Directed Expander Decompositions
by: Sulser, Aurelio L., et al.
Published: (2024)

Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings
by: Kyng, Rasmus, et al.
Published: (2025)

A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition
by: Gutenberg, Maximilian Probst, et al.
Published: (2025)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
by: Das, Debarati, et al.
Published: (2026)

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
by: Ashvinkumar, Vikrant, et al.
Published: (2026)

Optimal Electrical Oblivious Routing on Expanders
by: Florescu, Cella, et al.
Published: (2024)

A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows
by: Gutenberg, Maximilian Probst, et al.
Published: (2025)

Approximation Algorithms for D-optimal Design
by: Singh, Mohit, et al.
Published: (2018)

Approximation Algorithms for Combinatorial Optimization with Predictions
by: Antoniadis, Antonios, et al.
Published: (2024)

A Simple Dynamic Spanner via APSP
by: Kyng, Rasmus, et al.
Published: (2024)

Bootstrapping Dynamic APSP via Sparsification
by: Kyng, Rasmus, et al.
Published: (2024)

A Simple Approximation Algorithm for Optimal Decision Tree
by: Zhuo, Zhengjia, et al.
Published: (2025)

Improved Approximations for Hard Graph Problems using Predictions
by: Aamand, Anders, et al.
Published: (2025)

On Socially Fair Low-Rank Approximation and Column Subset Selection
by: Song, Zhao, et al.
Published: (2024)

MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation
by: Hayderi, Alexandre, et al.
Published: (2024)

Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach
by: Yang, Yichun, et al.
Published: (2024)

Expander Hierarchies for Normalized Cuts on Graphs
by: Hanauer, Kathrin, et al.
Published: (2024)

GEFL: Extended Filtration Learning for Graph Classification
by: Zhang, Simon, et al.
Published: (2024)

Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
by: Kamath, Gautam, et al.
Published: (2025)

Deterministic Almost-Linear-Time Gomory-Hu Trees
by: Abboud, Amir, et al.
Published: (2025)

Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach
by: Shakiba, Ali
Published: (2023)

Exact and Approximate Algorithms for Polytree Learning
by: Harviainen, Juha, et al.
Published: (2026)

Are Graph Neural Networks Optimal Approximation Algorithms?
by: Yau, Morris, et al.
Published: (2023)

Label-consistent clustering for evolving data
by: Gadekar, Ameet, et al.
Published: (2025)

Collaborative Learning with Different Labeling Functions
by: Deng, Yuyang, et al.
Published: (2024)

Sublinear Time Quantum Algorithm for Attention Approximation
by: Song, Zhao, et al.
Published: (2026)

Weak to Strong Learning from Aggregate Labels
by: Makhija, Yukti, et al.
Published: (2024)

Detection of Common Subtrees with Identical Label Distribution
by: Azaïs, Romain, et al.
Published: (2023)

Guessing Efficiently for Constrained Subspace Approximation
by: Bhaskara, Aditya, et al.
Published: (2025)

The Space Complexity of Approximating Logistic Loss
by: Dexter, Gregory, et al.
Published: (2024)

Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets
by: Lee, Russell, et al.
Published: (2022)

Distribution Learning Meets Graph Structure Sampling
by: Bhattacharyya, Arnab, et al.
Published: (2024)

Dynamic Spectral Clustering with Provable Approximation Guarantee
by: Laenen, Steinar, et al.
Published: (2024)

Reweighted Solutions for Weighted Low Rank Approximation
by: Woodruff, David P., et al.
Published: (2024)

Efficient Testable Learning of General Halfspaces with Adversarial Label Noise
by: Diakonikolas, Ilias, et al.
Published: (2024)

Incremental Approximate Single-Source Shortest Paths with Predictions
by: McCauley, Samuel, et al.
Published: (2025)