Buchumschlag

Improved Approximations for Hard Graph Problems using Predictions

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Aamand, Anders, Chen, Justin Y., Gollapudi, Siddharth, Silwal, Sandeep, Wu, Hao
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Machine Learning Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Learning-Augmented Frequent Directions
von: Aamand, Anders, et al.
Veröffentlicht: (2025)

How fast can you find a good hypothesis?
von: Aamand, Anders, et al.
Veröffentlicht: (2025)

On the Structure of Replicable Hypothesis Testers
von: Aamand, Anders, et al.
Veröffentlicht: (2025)

Skirting Additive Error Barriers for Private Turnstile Streams
von: Aamand, Anders, et al.
Veröffentlicht: (2026)

Statistical-Computational Trade-offs for Density Estimation
von: Aamand, Anders, et al.
Veröffentlicht: (2024)

Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
von: Aamand, Anders, et al.
Veröffentlicht: (2025)

Differentially Private Gomory-Hu Trees
von: Aamand, Anders, et al.
Veröffentlicht: (2024)

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
von: Silwal, Sandeep, et al.
Veröffentlicht: (2025)

Optimal Algorithms for Augmented Testing of Discrete Distributions
von: Aliakbarpour, Maryam, et al.
Veröffentlicht: (2024)

A Bi-metric Framework for Fast Similarity Search
von: Xu, Haike, et al.
Veröffentlicht: (2024)

On the Hardness of Approximation of the Fair k-Center Problem
von: Thejaswi, Suhas
Veröffentlicht: (2026)

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
von: Gao, Jie, et al.
Veröffentlicht: (2025)

Sample-Efficient Optimization over Generative Priors via Coarse Learnability
von: Awasthi, Pranjal, et al.
Veröffentlicht: (2025)

Compact Conformal Subgraphs
von: Gollapudi, Sreenivas, et al.
Veröffentlicht: (2026)

Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem
von: Blum, Avrim, et al.
Veröffentlicht: (2024)

Efficiently Computing Similarities to Private Datasets
von: Backurs, Arturs, et al.
Veröffentlicht: (2024)

Near-Optimal Trace Reconstruction for Mildly Separated Strings
von: Aamand, Anders, et al.
Veröffentlicht: (2024)

MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation
von: Hayderi, Alexandre, et al.
Veröffentlicht: (2024)

An Approximation Algorithm for Graph Label Selection
von: John, Josia, et al.
Veröffentlicht: (2026)

Approximation Algorithms for Combinatorial Optimization with Predictions
von: Antoniadis, Antonios, et al.
Veröffentlicht: (2024)

Algorithms with Calibrated Machine Learning Predictions
von: Shen, Judy Hanwen, et al.
Veröffentlicht: (2025)

Incremental Approximate Single-Source Shortest Paths with Predictions
von: McCauley, Samuel, et al.
Veröffentlicht: (2025)

Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach
von: Yang, Yichun, et al.
Veröffentlicht: (2024)

Learning the Inverse Temperature of Ising Models under Hard Constraints using One Sample
von: Chauhan, Rohan, et al.
Veröffentlicht: (2025)

Robust Streaming Against Low-Memory Adversaries
von: Ben-Eliezer, Omri, et al.
Veröffentlicht: (2025)

Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point
von: Chen, Hongjie, et al.
Veröffentlicht: (2025)

Computational and Statistical Hardness of Calibration Distance
von: Qiao, Mingda
Veröffentlicht: (2026)

Improved Hardness of Approximation for Geometric Bin Packing
von: Ray, Arka, et al.
Veröffentlicht: (2023)

Improving Online Algorithms via ML Predictions
von: Kumar, Ravi, et al.
Veröffentlicht: (2024)

Improved Bounds for Online Facility Location with Predictions
von: Fotakis, Dimitris, et al.
Veröffentlicht: (2021)

Optimal Approximate Matrix Multiplication over Sliding Windows
von: Yao, Ziqi, et al.
Veröffentlicht: (2025)

Hardness and Approximation Algorithms for Balanced Districting Problems
von: Dharangutte, Prathamesh, et al.
Veröffentlicht: (2025)

Fast and Accurate Triangle Counting in Graph Streams Using Predictions
von: Boldrin, Cristian, et al.
Veröffentlicht: (2024)

On the Problem of Best Arm Retention
von: Chen, Houshuang, et al.
Veröffentlicht: (2025)

Limits of Approximating the Median Treatment Effect
von: Addanki, Raghavendra, et al.
Veröffentlicht: (2024)

Energy-Efficient Scheduling with Predictions
von: Balkanski, Eric, et al.
Veröffentlicht: (2024)

Graph Neural Network-Informed Predictive Flows for Faster Ford-Fulkerson and PAC-Learnability
von: Wiesler, Eleanor, et al.
Veröffentlicht: (2026)

Guessing Efficiently for Constrained Subspace Approximation
von: Bhaskara, Aditya, et al.
Veröffentlicht: (2025)

Approximation Algorithms for D-optimal Design
von: Singh, Mohit, et al.
Veröffentlicht: (2018)

The Space Complexity of Approximating Logistic Loss
von: Dexter, Gregory, et al.
Veröffentlicht: (2024)