Learning-Augmented Algorithms

Ask about this topic

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

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

  1. Online Fair Division with Frequency Predictions

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

    Harvard University, USA · University of Oxford, UK

  2. Robust Non-Clairvoyant Scheduling with Classification Models

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

    Univ. Marie et Louis Pasteur, CNRS, institut FEMTO-ST, F-25000 Besançon, France · Université de Lorraine, LCOMS, Metz, France

  3. Understanding Private Evolution as Learning-Augmented Clustering

    Sep 29, 2026Audra McMillan, Kunal Talwar, Felix ZhouDifferentially Private Synthetic Data GenerationSynthetic Data Generation

    Apple · Yale University

  4. Predictive Dual Smoothing for Column Generation

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

    KU Leuven · TU Delft · Cornell Tech

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

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

    School of Artificial Intelligence and Automation Huazhong University of Science and Technology Wuhan, Hubei 430074, China · School of Computer Science and Technology Huazhong University of Science and Technology Wuhan, Hubei 430074, China

  6. Augmented Hypothesis Testing with Persona-Based LLM Simulations

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

    Amazon Luxembourg, Luxembourg · Amazon Barcelona, Spain

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

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

    Amazon RME · IE University, Department of Operations · Reinforcement Learning Research Lab, UniPD

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

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

    School of Software Technology, Zhejiang University, Ningbo, China · School of Computer Science and Engineering, Nanyang Technological University, Singapore, Singapore · College of Computer Science and Technology, Zhejiang University, Hangzhou, China +1

  9. Prediction-Assisted Pricing and Admission for LLM APIs with Stochastic Token Consumption

    Sep 1, 2026Patrick WongLLM ServingLearning-Augmented Algorithms

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

    Aug 27, 2026Fredy PokouOnline Resource AllocationLearning-Augmented Algorithms

    MRE, CRIStAL · Inria, University of Lille, CNRS, Centrale Lille Villeneuve-d’Ascq, France

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

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

    State Key Laboratory of Novel SoftwareTechnology, Nanjing University · School of Artificial Intelligence,Nanjing University · State Key Laboratory of Technology and Equipment for Defense Against Power System Operational Risks, Nari Technology Co., Ltd.

  12. MARA: Flow-Matching-Guided Multi-Agent Resource Allocation for Computational Resource Efficient Learning

    Aug 10, 2026Hanye Zhao, Muning Wen, Yong Yu +1Learning-Augmented AlgorithmsOnline Resource Allocation

    Shanghai Jiao Tong University

  13. Learning to Trace Seiberg Dualities

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

    Department of Physics and Astronomy, University of Pennsylvania, 209 South 33rd Street, Philadelphia, PA 19104, USA · Department of Physics, University of Wisconsin–Madison, 1150 University Avenue, Madison, WI 53706, USA

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

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

    Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China

  15. Online Fair Division with Budget Constraints

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

    Department of Computer Science, University of Oxford, UK

  16. Memory-Computation Tradeoffs in Semi Amortized Parametric Optimization

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

    Department of Electrical and Computer Engineering, Johns Hopkins University · Department of Applied Mathematics and Statistics, Johns Hopkins University Baltimore, MD 21218, USA

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

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

    School of Information, Central University of Finance and Economics Beijing 102206, China

  18. Sensitivity Sampling with Predictions for k-Means Clustering

    Jul 6, 2026Cristian Boldrin, Fabio VandinClusteringImportance Sampling

    University of Padova, Padova, Italy

  19. TSP with Predictions: Heatmap to Tour with Provable Guarantees

    Jul 4, 2026Marek Eliáš, Fabrizio Grandoni, Adam Polak +1Traveling Salesperson ProblemCombinatorial Optimization

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

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

    LIGHTSPEED, Tencent · Shenzhen, China · The Chinese University of Hong Kong +1

  21. Asymptotically Optimal Learning for Parametric Prophet Inequalities

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

    FairPlay Team, CREST, ENSAE, Institut Polytechnique de Paris · UFR IM2AG, Université Grenoble Alpes · Criteo AI Lab

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

    Jun 24, 2026Yan ZhouResidual LearningNonparametric Regression

    School of Mathematics and Statistics, Changsha University of Science and Technology.

  23. Learning-Augmented Algorithms for Online Vertex Cover

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

    Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China

  24. Learning Augmented Exact Exponential Algorithms

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

    ITMO University

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

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

    The University of Tokyo, Tokyo, Japan · Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

  26. Learning-Augmented Online Minimization with Dual Predictions

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

    University of Oxford, United Kingdom

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

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

    Institute for Intelligent Networked Systems, Northeastern University (NU), Boston, MA, USA. · SoftBank Corp. (SB), Japan.

  28. Towards Optimal Robustness in Learning-Augmented Paging

    May 31, 2026Peng Chen, Hailiang Zhao, Xueyan Tang +2Competitive AnalysisLearning-Augmented Algorithms

    Zhejiang University, Hangzhou, China · Nanyang Technological University, Singapore · Nanjing University of Aeronautics and Astronautics, Nanjing, China

  29. Parsimonious Learning-Augmented Online Metric Matching

    May 26, 2026Yongho Shin, Phanu VajanopathLearning-Augmented Algorithms

    Institute of Computer Science, University of Wrocław, Wrocław, Poland.

  30. Learning-Augmented Online Scheduling with Parsimonious Preemption

    May 22, 2026Mugen Blue, Sungjin Im, Alexander LindermayrCombinatorial OptimizationLearning-Augmented Algorithms

    University of California, Santa Cruz, US. · Institut für Mathematik, Technische Universität Berlin, Germany.