Learning-Augmented Algorithms

Overview

The field studies how predictions can help algorithms make better decisions without making them depend on perfect advice. Common approaches blend predictions with robust online strategies, measure performance as prediction error changes, or use predictions to guide search, warm-start optimization, and reduce sampling or memory costs. Applications include scheduling, caching, matching, clustering, graph problems, and mathematical optimization, with guarantees often expressed as trade-offs between performance with accurate predictions and worst-case robustness. Tight bounds are now known for some problems, but a key tension remains: practical gains must be weighed against prediction costs, distribution shift, and whether theoretical guarantees reflect end-to-end system performance.

Latest papers

CardsList

58 papers4 papers in the last four weeks, down 20% on the four weeks before. 0.0% of all new papers.

  1. Collective Tree Exploration with Predictions

    Nov 12, 2026Romain Cosson, Yichen Huang, Michael Mitzenmacher +1Tree SearchMulti-Robot Exploration

  2. Multiple-Choice Secretary Problem with Predictions

    Nov 10, 2026Jing Yuan, Qi Cai, Xin Gao +1Sequential Decision MakingLearning-Augmented Algorithms

  3. Sparse Predict and Demote: Optimal Scheduling with Minimal Size Advice

    Nov 6, 2026Chengyi Liu, Thodoris Lykouris, Junxuan Shen +1Queueing TheoryLearning-Augmented Algorithms

  4. Online Fair Division with Frequency Predictions

    Oct 25, 2026Tzeh Yuan Neoh, Nicholas TehFair Resource AllocationLearning-Augmented Algorithms

  5. Robust Non-Clairvoyant Scheduling with Classification Models

    Oct 1, 2026Anthony Dugois, Vincent Fagnon, Giorgio LucarelliRobust OptimizationLearning-Augmented Algorithms

  6. Predictive Dual Smoothing for Column Generation

    Sep 28, 2026Senne Berden, Noah Schutte, Andrea Lodi +1Primal-Dual OptimizationLinear Programming

  7. Compressing Value Predictions for Learning-Augmented Metrical Task Systems

    Sep 27, 2026Sizhe Li, Yecheng Li, Kun HeLearning-Augmented Algorithms

  8. Augmented Hypothesis Testing with Persona-Based LLM Simulations

    Sep 21, 2026Ziyad Benomar, Aymen Al Marjani, Paul Missault +1A/b TestingLearning-Augmented Algorithms

  9. Learning-Augmented Optimization for Strategic Two-Echelon Spare Parts Network Design

    Sep 11, 2026Donato Maragno, Marco Caserta, Alberto Sinigaglia +3Surrogate-Assisted OptimizationMetaheuristic Optimization

  10. Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications

    Sep 4, 2026Hailiang Zhao, Xueyan Tang, Peng Chen +4Learning-Augmented Algorithms

  11. Learning-Augmented Online Allocation under Unreliable Advice: Robustness, Exposure Fairness, and Distribution Shift

    Aug 27, 2026Fredy PokouOnline Resource AllocationLearning-Augmented Algorithms

  12. Learning Early-to-Final Solution Consistency for MILP Acceleration

    Aug 20, 2026Guanlin Li, Chengrui Gao, Chenguang Wang +6Mixed-Integer Linear ProgrammingLearning to Optimize

  13. Learning to Trace Seiberg Dualities

    Jul 30, 2026Jonathan J. Heckman, Shani Meynet, Alessandro Mininno +1TransformerScientific ML

  14. Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays

    Jul 30, 2026Tianhang Lu, Runtian Ren, Shengcai Liu +1Competitive AnalysisLearning-Augmented Algorithms

  15. Online Fair Division with Budget Constraints

    Jul 25, 2026Saar Cohen, Nicholas Teh, Paul W. Goldberg +1Fair Resource AllocationLearning-Augmented Algorithms

  16. Memory-Computation Tradeoffs in Semi Amortized Parametric Optimization

    Jul 22, 2026Shijie Pan, Agustin Castellano, Zeyu Shen +1Learning to OptimizeLearning-Augmented Algorithms

  17. CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees

    Jul 16, 2026Haifeng Li, Mo HaiCombinatorial OptimizationLearning-Augmented Algorithms

  18. Sensitivity Sampling with Predictions for k-Means Clustering

    Jul 6, 2026Cristian Boldrin, Fabio VandinClusteringImportance Sampling

  19. When Classic Cache Policies Fail: Learning-Augmented Replacement for Semantic Retrieval Buffers

    Jul 1, 2026Yushi Sun, Bowen Cao, Wai LamLearning-Augmented AlgorithmsSemantic Caching

  20. Asymptotically Optimal Learning for Parametric Prophet Inequalities

    Jun 25, 2026Jung-hun Kim, Anna Grebennikova, Vianney PerchetSequential Decision MakingOptimal Stopping

  21. Black-Box Assisted Regression: Phase Transitions and Minimax Optimality

    Jun 24, 2026Yan ZhouResidual LearningNonparametric Regression

  22. Learning-Augmented Algorithms for Online Vertex Cover

    Jun 22, 2026Tianhang Lu, Runtian Ren, Shengcai LiuCompetitive AnalysisCombinatorial Optimization

  23. Learning Augmented Exact Exponential Algorithms

    Jun 17, 2026Tatiana Belova, Yuriy Dementiev, Danil SagunovLearning-Augmented Algorithms

  24. Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling

    Jun 11, 2026Kaito Baba, Evripidis Bampis, Giorgos MitropoulosCombinatorial OptimizationLearning-Augmented Algorithms

  25. Learning-Augmented Online Minimization with Dual Predictions

    Jun 3, 2026Christian Coester, Alexa Tudose, Alexander TuroczyCombinatorial OptimizationLearning-Augmented Algorithms

  26. AUGUSTE: Online-Learning dApp for Predictive URLLC Scheduling

    Jun 2, 2026Maxime Elkael, Michele Polese, Yunseong Lee +2Wireless CommunicationsWireless Resource Allocation