Learning-Augmented Algorithms

Follow this topic Ask about this topic

Momentum

5 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 39

All topics

Robust Non-Clairvoyant Scheduling with Classification Models
Oct 1, 2026Anthony Dugois, Vincent Fagnon, Giorgio LucarelliRobust Optimization Learning-Augmented Algorithms
Univ. Marie et Louis Pasteur, CNRS, institut FEMTO-ST, F-25000 Besançon, France · Université de Lorraine, LCOMS, Metz, France
Predictive Dual Smoothing for Column Generation
Sep 28, 2026Senne Berden, Noah Schutte, Andrea Lodi +1Primal-Dual Optimization Linear Programming
KU Leuven · TU Delft · Cornell Tech
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
Augmented Hypothesis Testing with Persona-Based LLM Simulations
Sep 21, 2026Ziyad Benomar, Aymen Al Marjani, Paul Missault +1A/b Testing Learning-Augmented Algorithms
Amazon Luxembourg, Luxembourg · Amazon Barcelona, Spain
Learning-Augmented Optimization for Strategic Two-Echelon Spare Parts Network Design
Sep 14, 2026Donato Maragno, Marco Caserta, Alberto Sinigaglia +3Surrogate-Assisted Optimization Metaheuristic Optimization
Amazon RME · IE University, Department of Operations · Reinforcement Learning Research Lab, UniPD
Prediction-Assisted Pricing and Admission for LLM APIs with Stochastic Token Consumption
Sep 1, 2026Patrick WongLLM Serving Learning-Augmented Algorithms
MARA: Flow-Matching-Guided Multi-Agent Resource Allocation for Computational Resource Efficient Learning
Aug 10, 2026Hanye Zhao, Muning Wen, Yong Yu +1Learning-Augmented Algorithms Online Resource Allocation
Shanghai Jiao Tong University
Learning to Trace Seiberg Dualities
Jul 30, 2026Jonathan J. Heckman, Shani Meynet, Alessandro Mininno +1Transformer Scientific 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
Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays
Jul 30, 2026Tianhang Lu, Runtian Ren, Shengcai Liu +1Competitive Analysis Learning-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
Online Fair Division with Budget Constraints
Jul 25, 2026Saar Cohen, Nicholas Teh, Paul W. Goldberg +1Fair Resource Allocation Learning-Augmented Algorithms
Department of Computer Science, University of Oxford, UK
Memory-Computation Tradeoffs in Semi Amortized Parametric Optimization
Jul 22, 2026Shijie Pan, Agustin Castellano, Zeyu Shen +1Learning to Optimize Learning-Augmented Algorithms
Department of Electrical and Computer Engineering, Johns Hopkins University · Department of Applied Mathematics and Statistics, Johns Hopkins University Baltimore, MD 21218, USA
CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees
Jul 16, 2026Haifeng Li, Mo HaiCombinatorial Optimization Learning-Augmented Algorithms
School of Information, Central University of Finance and Economics Beijing 102206, China
Sensitivity Sampling with Predictions for k-Means Clustering
Jul 6, 2026Cristian Boldrin, Fabio VandinClustering Importance Sampling
University of Padova, Padova, Italy
TSP with Predictions: Heatmap to Tour with Provable Guarantees
Jul 4, 2026Marek Eliáš, Fabrizio Grandoni, Adam Polak +1Traveling Salesperson Problem Combinatorial Optimization
When Classic Cache Policies Fail: Learning-Augmented Replacement for Semantic Retrieval Buffers
Jul 1, 2026Yushi Sun, Bowen Cao, Wai LamLearning-Augmented Algorithms Semantic Caching
LIGHTSPEED, Tencent · Shenzhen, China · The Chinese University of Hong Kong +1
Asymptotically Optimal Learning for Parametric Prophet Inequalities
Jun 25, 2026Jung-hun Kim, Anna Grebennikova, Vianney PerchetSequential Decision Making Optimal Stopping
FairPlay Team, CREST, ENSAE, Institut Polytechnique de Paris · UFR IM2AG, Université Grenoble Alpes · Criteo AI Lab
Black-Box Assisted Regression: Phase Transitions and Minimax Optimality
Jun 24, 2026Yan ZhouResidual Learning Nonparametric Regression
School of Mathematics and Statistics, Changsha University of Science and Technology.
Learning-Augmented Algorithms for Online Vertex Cover
Jun 22, 2026Tianhang Lu, Runtian Ren, Shengcai LiuCompetitive Analysis Combinatorial 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
Learning Augmented Exact Exponential Algorithms
Jun 17, 2026Tatiana Belova, Yuriy Dementiev, Danil SagunovLearning-Augmented Algorithms
ITMO University
Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling
Jun 11, 2026Kaito Baba, Evripidis Bampis, Giorgos MitropoulosCombinatorial Optimization Learning-Augmented Algorithms
The University of Tokyo, Tokyo, Japan · Sorbonne Université, CNRS, LIP6, F-75005 Paris, France
Learning-Augmented Online Minimization with Dual Predictions
Jun 3, 2026Christian Coester, Alexa Tudose, Alexander TuroczyCombinatorial Optimization Learning-Augmented Algorithms
University of Oxford, United Kingdom
AUGUSTE: Online-Learning dApp for Predictive URLLC Scheduling
Jun 2, 2026Maxime Elkael, Michele Polese, Yunseong Lee +2Wireless Communications Wireless Resource Allocation
Institute for Intelligent Networked Systems, Northeastern University (NU), Boston, MA, USA. · SoftBank Corp. (SB), Japan.
Towards Optimal Robustness in Learning-Augmented Paging
May 31, 2026Peng Chen, Hailiang Zhao, Xueyan Tang +2Competitive Analysis Learning-Augmented Algorithms
Zhejiang University, Hangzhou, China · Nanyang Technological University, Singapore · Nanjing University of Aeronautics and Astronautics, Nanjing, China
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.
Learning-Augmented Online Scheduling with Parsimonious Preemption
May 22, 2026Mugen Blue, Sungjin Im, Alexander LindermayrCombinatorial Optimization Learning-Augmented Algorithms
University of California, Santa Cruz, US. · Institut für Mathematik, Technische Universität Berlin, Germany.
The Secretary Problem with a Stochastic Precursor
May 21, 2026Franziska Eberle, Alexander LindermayrSequential Decision Making Optimal Stopping
Institut für Mathematik, Technische Universität Berlin, Germany.
Learning-Accelerated Optimization-based Trajectory Planning for Cooperative Aerial-Ground Handover Missions
May 19, 2026Jingshan Chen, Bochen Yu, Henrik Ebel +1Multi-Robot Motion Planning Trajectory Optimization
Institute of Engineering and Computational Mechanics, University of Stuttgart, 70569 Stuttgart, Germany · Mechanical Engineering, LUT University, 53850 Lappeenranta, Finland
Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming
May 18, 2026Tung Quoc Le, Anh Tuan Nguyen, Viet Anh NguyenMixed-Integer Linear Programming Learning to Optimize
Université Grenoble Alpes, LJK, CNRS, Grenoble INP, 38000 Grenoble, France · Carnegie Mellon University, Machine Learning Department · Chinese University of Hong Kong, Department of Systems Engineering and Engineering Management.
Low-Cost Labels, Reliable Choices: Rollout-Calibrated Hyper-Heuristics for Job Shop Scheduling
May 11, 2026Junhao Wei, Yanxiao Li, Yifu Zhao +8Selective Prediction Metaheuristic Optimization
Faculty of Applied Sciences, Macao Polytechnic University, Macao, 999078, China · College of Animal Science and Technology, Zhongkai University of Agriculture and Engineering, Guangzhou, 510225, China · 4Macao Polytechnic University, Macao, 999078, China
Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts
May 10, 2026Ilay Yavlovich, Jad Agbaria, Muhamed Mhamed +2Neural Network Optimization Combinatorial Optimization
Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology, Haifa, Israel.

Oct 1, 2026, cs.LGJ/K move · Enter open · S save

Robust Non-Clairvoyant Scheduling with Classification Models

Anthony Dugois, Vincent Fagnon, Giorgio Lucarelli

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

Robust Optimization Learning-Augmented Algorithms

Open paper AskPDF arXiv

We study the classical single-machine scheduling problem of minimizing the sum of completion times of jobs in a non-clairvoyant setting, where the processing time of each job remains unknown until its completion. This is a hard problem for which no constant competitive algorithm is possible. Inspired by robust optimization and learning-augmented algorithms, we introduce a novel robustness framework that leverages structural information provided by a classification model to overcome this limitation. Specifically, we assume that jobs are partitioned into classes and we have access to the confusion matrix of the classifier, whose entry

(k,\ell)

indicates the number of jobs predicted to belong to class~

k

but that actually belong to class~

\ell

. In this manner, we are able to characterize uncertainty as a set of permutations within each predicted class, rather than as a collection of discrete numerical scenarios, avoiding the computational difficulty of classical robust metrics, such as Min-Max and Min-Max Regret. In addition to these worst-case metrics, we also consider the expected objective over all scenarios. We first propose an optimal non-adaptive strategy that is oblivious with respect to all three robust criteria. We then investigate adaptive and randomized algorithms, showing that they can outperform the optimal non-adaptive strategy when the matrix exhibits particular structural properties.

Momentum

Related topics

Latest papers 39