Cover Image

Approximation Algorithms for Combinatorial Optimization with Predictions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Antoniadis, Antonios, Eliáš, Marek, Polak, Adam, Venzin, Moritz
Format:	Preprint
Published:	2024
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

Stronger adversaries grow cheaper forests: online node-weighted Steiner problems
by: Borst, Sander, et al.
Published: (2024)

Connectivity Oracles for Predictable Vertex Failures
by: Hu, Bingbing, et al.
Published: (2023)

Algorithms for Caching and MTS with reduced number of predictions
by: Sadek, Karim Abdel, et al.
Published: (2024)

Learning-Augmented Algorithms with Explicit Predictors
by: Elias, Marek, et al.
Published: (2024)

On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
by: Antoniadis, Antonios, et al.
Published: (2020)

Online Algorithms with Uncertainty-Quantified Predictions
by: Sun, Bo, et al.
Published: (2023)

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

An Approximation Algorithm for Graph Label Selection
by: John, Josia, et al.
Published: (2026)

Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity
by: Amanatidis, Georgios, et al.
Published: (2021)

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

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

To buy or not to buy: deterministic rent-or-buy problems on node-weighted graphs
by: Borst, Sander, et al.
Published: (2025)

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

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

Algorithms with Calibrated Machine Learning Predictions
by: Shen, Judy Hanwen, et al.
Published: (2025)

A Model for Combinatorial Dictionary Learning and Inference
by: Blum, Avrim, et al.
Published: (2024)

Adversarial Attacks on Combinatorial Multi-Armed Bandits
by: Balasubramanian, Rishab, et al.
Published: (2023)

Improving Online Algorithms via ML Predictions
by: Kumar, Ravi, et al.
Published: (2024)

Prediction-Specific Design of Learning-Augmented Algorithms
by: Li, Sizhe, et al.
Published: (2025)

Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach
by: Lee, Changyeol, et al.
Published: (2025)

Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms
by: Lechowicz, Adam, et al.
Published: (2023)

Testing Noise Assumptions of Learning Algorithms
by: Goel, Surbhi, et al.
Published: (2025)

Signal-Aware Workload Shifting Algorithms with Uncertainty-Quantified Predictors
by: Johnson, Ezra, et al.
Published: (2025)

Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions
by: Aliakbarpour, Maryam, et al.
Published: (2026)

Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits
by: Ye, Zichun, et al.
Published: (2025)

Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better
by: Balmaseda, Vicente, et al.
Published: (2024)

Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds
by: Klivans, Adam R., et al.
Published: (2024)

Discretely Beyond $1/e$: Guided Combinatorial Algorithms for Submodular Maximization
by: Chen, Yixin, et al.
Published: (2024)

Stochastic scheduling with Bernoulli-type jobs through policy stratification
by: Antoniadis, Antonios, et al.
Published: (2025)

Combinatorial optimization of the coefficient of determination
by: Harary, Marc
Published: (2024)

A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube
by: Chandrasekaran, Gautam, et al.
Published: (2025)

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

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

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

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

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

Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification
by: Rohatgi, Dhruv, et al.
Published: (2025)

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)

Learning-Augmented Online Covering Problems
by: Ameli, Afrouz Jabal, et al.
Published: (2025)