ALPS

234 papers


  • Distributed Graph Algorithms with Predictions
    Boyar, Ellen, Larsen
    arXiv '25
    distributed algorithms
    graph problems
  • Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
    Dong, Peng, Vakilian
    arXiv '24
    approximation
    graph problems
    streaming
  • Fair Secretaries with Unfair Predictions
    Balkanski, Ma, Maggiori
    arXiv '24
    online
    secretary
  • Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems
    Grigorescu, Lin, Song
    arXiv '24
    online
    packing
  • Strategic Facility Location via Predictions
    Chen, Gravin, Im
    arXiv '24
    facility location
    game theory / mechanism design
  • A short note about the learning-augmented secretary problem
    Choo, Ling
    arXiv '24
    online
    secretary
  • Learning-Augmented Robust Algorithmic Recourse
    Kayastha, Gkatzelis, Jabbari
    arXiv '24
    robustness
  • The Secretary Problem with Predicted Additive Gap
    Braun, Sarkar
    arXiv '24
    online
    secretary
  • Binary Search with Distributional Predictions
    Dinitz, Im, Lavastida, Moseley, Niaparast, Vassilvitskii
    arXiv '24
    NeurIPS '24
    dynamic / data structure
    search
  • Fast and Accurate Triangle Counting in Graph Streams Using Predictions
    Boldrin, Vandin
    arXiv '24
    streaming
  • Comparing the Hardness of Online Minimization and Maximization Problems with Predictions
    Berg
    arXiv '24
    online
  • Learning-Augmented Frequency Estimation in Sliding Windows
    Shahout, Sabek, Mitzenmacher
    arXiv '24
    streaming
  • CarbonClipper: Optimal Algorithms for Carbon-Aware Spatiotemporal Workload Management
    Lechowicz, Christianson, Sun, Bashir, Hajiesmaili, Wierman, Shenoy
    arXiv '24
    allocation / matching
    online
  • Clock Auctions Augmented with Unreliable Advice
    Gkatzelis, Schoepflin, Tan
    arXiv '24
    auctions
    game theory / mechanism design
  • Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms
    Angelopoulos, Dürr, Elenter, Lefki
    arXiv '24
    online
  • Complexity Classes for Online Problems with and without Predictions
    Berg, Boyar, Favrholdt, Larsen
    arXiv '24
    online
  • A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives
    Grigorescu, Lin, Song
    arXiv '24
    online
    packing
    scheduling
  • Warm-starting Push-Relabel
    Davies, Vassilvitskii, Wang
    arXiv '24
    graph problems
    running time
  • Online Classification with Predictions
    Raman, Tewari
    arXiv '24
    learning
    online
  • Equilibria in multiagent online problems with predictions
    Istrate, Bonchis, Bogdan
    arXiv '24
    game theory / mechanism design
    online
    rent-or-buy
  • Online Lead Time Quotation with Predictions
    Huo, Tianming; Cheung, Wang Chi
    SSRN '24
    online
    scheduling
  • Competitive strategies to use "warm start" algorithms with predictions
    Srinivas, Blum
    arXiv '24
    multiple predictions
    online
  • Non-clairvoyant Scheduling with Partial Predictions
    Benomar, Perchet
    arXiv '24
    ICML '24
    online
    parsimonious / succinct
    scheduling
  • PCF Learned Sort: a Learning Augmented Sort Algorithm with O(n log log n) Expected Complexity
    Sato, Matsui
    arXiv '24
    running time
    sorting
  • Learning-Augmented Algorithms with Explicit Predictors
    Elias, Kaplan, Mansour, Moran
    arXiv '24
    allocation / matching
    caching / paging
    online
    scheduling
  • To Trust or Not to Trust: Assignment Mechanisms with Predictions in the Private Graph Model
    Colini-Baldeschi, Klumper, Schäfer, Tsikiridis
    arXiv '24
    EC '24
    allocation / matching
    game theory / mechanism design
    graph problems
  • Best of Many in Both Worlds: Online Resource Allocation with Predictions under Unknown Arrival Model
    An, Li, Moseley, Visotsky
    arXiv '24
    allocation / matching
    online
  • Learning-Augmented Skip Lists
    Fu, Seo, Zhou
    arXiv '24
    dynamic / data structure
    search
  • Accelerating Matroid Optimization through Fast Imprecise Oracles
    Eberle, Hommelsheim, Lindermayr, Liu, Megow, Schlöter
    arXiv '24
    matroid
    running time
    two-oracle
  • Max-Cut with ε-Accurate Predictions
    Cohen-Addad, d'Orsi, Gupta, Lee, Panigrahi
    arXiv '24
    approximation
    graph problems
  • Online Covering with Multiple Experts
    Kevi, Nguyen
    arXiv '23
    covering
    multiple predictions
    online
  • On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rental
    Shin, Lee, An
    arXiv '23
    online
    rent-or-buy
  • Credence: Augmenting Datacenter Switch Buffer Sharing with ML Predictions
    Addanki, Pacut, Schmid
    arXiv '24
    NSDI '24
    networks
    online
    queueing
  • Online Graph Coloring with Predictions
    Antoniadis, Broersma, Meng
    arXiv '23
    ISCO '24
    graph problems
    online
  • Randomized Strategic Facility Location with Predictions
    Balkanski, Gkatzelis, Shahkarami
    arXiv '24
    NeurIPS '24
    facility location
    game theory / mechanism design
  • Parsimonious Learning-Augmented Approximations for Dense Instances of NP-hard Problems
    Bampis, Escoffier, Xefteris
    arXiv '24
    ICML '24
    approximation
    graph problems
    running time
  • MAC Advice for Facility Location Mechanism Design
    Barak, Gupta, Talgam-Cohen
    arXiv '24
    NeurIPS '24
    facility location
    game theory / mechanism design
  • Learning-Augmented Priority Queues
    Benomar, Coester
    arXiv '24
    NeurIPS '24
    dynamic / data structure
    shortest path
    sorting
    two-oracle
  • Online Bin Covering with Frequency Predictions
    Berg, Kamali
    arXiv '24
    SWAT '24
    covering
    online
  • Learning-augmented Maximum Independent Set
    Braverman, Dharangutte, Shah, Wang
    APPROX/RANDOM '24
    arXiv '24
    approximation
    graph problems
  • Randomized learning-augmented auctions with revenue guarantees
    Caragiannis, Kalantzis
    arXiv '24
    IJCAI '24
    auctions
    game theory / mechanism design
  • Online bipartite matching with imperfect advice
    Choo, Gouleakis, Ling, Bhattacharyya
    arXiv '24
    ICML '24
    allocation / matching
    online
  • Mechanism Design Augmented with Output Advice
    Christodoulou, Sgouritsa, Vlachos
    arXiv '24
    NeurIPS '24
    auctions
    facility location
    game theory / mechanism design
    scheduling
  • Plant-and-Steal: Truthful Fair Allocations via Predictions
    Cohen, Eden, Eden, Vasilyan
    arXiv '24
    NeurIPS '24
    allocation / matching
    game theory / mechanism design
  • Learning-Based Algorithms for Graph Searching Problems
    DePavia, Tani, Vakilian
    AISTATS '24
    arXiv '24
    exploration
    online
    search
  • Online Simple Knapsack with Bounded Predictions
    Gehnen, Lotze, Rossmanith
    STACS '24
    online
    packing
  • Connectivity Oracles for Predictable Vertex Failures
    Hu, Kosinas, Polak
    arXiv '23
    ESA '24
    dynamic / data structure
    network design
  • Chasing Convex Functions with Long-term Constraints
    Lechowicz, Christianson, Sun, Bashir, Hajiesmaili, Wierman, Shenoy
    arXiv '24
    ICML '24
    k-server / MTS
    online
    search
  • Disentangling Linear Quadratic Control with Untrusted ML Predictions
    Li, Liu, Yue
    NeurIPS '24
    linear quadratic control
    online
  • Incremental Topological Ordering and Cycle Detection with Predictions
    McCauley, Moseley, Niaparast, Singh
    arXiv '24
    ICML '24
    dynamic / data structure
    graph problems
    running time
  • Algorithms for Caching and MTS with Reduced Number of Predictions
    Sadek, Elias
    arXiv '24
    ICLR '24
    caching / paging
    k-server / MTS
    online
  • Robust Learning-Augmented Dictionaries
    Zeynali, Kamali, Hajiesmaili
    arXiv '24
    ICML '24
    dynamic / data structure
    search
  • Cost-Driven Data Replication with Predictions
    Zuo, Tang, Lee
    arXiv '24
    SPAA '24
    online
  • Learning-Augmented Algorithms for the Bahncard Problem
    Zhao, Tang, Chen, Deng
    arXiv '24
    NeurIPS '24
    online
    rent-or-buy
  • Learning-Augmented Dynamic Submodular Maximization
    Agarwal, Balkanski
    arXiv '23
    dynamic / data structure
    running time
    submodular maximization
  • Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms
    Lechowicz, Christianson, Sun, Bashir, Hajiesmaili, Wierman, Shenoy
    arXiv '23
    SIGMETRICS/Performance '24
    online
    search
  • Online Algorithms with Uncertainty-Quantified Predictions
    Sun, Huang, Christianson, Hajiesmaili, Wierman
    arXiv '23
    ICML '24
    online
    rent-or-buy
    search
  • Online Mechanism Design with Predictions
    Balkanski, Gkatzelis, Tan, Zhu
    arXiv '23
    EC '24
    auctions
    game theory / mechanism design
  • Competitive Auctions with Imperfect Predictions
    Lu, Wan, Zhang
    arXiv '23
    EC '24
    auctions
    game theory / mechanism design
  • On the Complexity of Algorithms with Predictions for Dynamic Graph Problems
    Henzinger, Lincoln, Saha, Seybold, Ye
    arXiv '23
    ITCS '24
    dynamic / data structure
    running time
  • On Dynamic Graph Algorithms with Predictions
    Brand, Forster, Nazari, Polak
    arXiv '23
    SODA '24
    dynamic / data structure
    graph problems
    running time
  • Learning-Augmented Metric Distortion via (p,q)-Veto Core
    Berger, Feldman, Gkatzelis, Tan
    arXiv '23
    EC '24
    game theory / mechanism design
  • Online Resource Allocation with Convex-set Machine-Learned Advice
    Golrezaei, Jaillet, Zhou
    arXiv '23
    allocation / matching
    online
  • The Predicted-Deletion Dynamic Model: Taking Advantage of ML Predictions, for Free
    Liu, Srinivas
    arXiv '23
    dynamic / data structure
    running time
  • Learning-Augmented Decentralized Online Convex Optimization in Networks
    Li, Yang, Wierman, Ren
    arXiv '23
    online
  • The Secretary Problem with Predictions
    Fujii, Yoshida
    arXiv '23
    Math. Oper. Res. '24
    online
    secretary
  • Time Fairness in Online Knapsack Problems
    Lechowicz, Sengupta, Sun, Kamali, Hajiesmaili
    arXiv '23
    ICLR '24
    allocation / matching
    online
    packing
  • The Nonstationary Newsvendor with (and without) Predictions
    An, Li, Moseley, Ravi
    arXiv '23
    online
  • Learning-Augmented Online Packet Scheduling with Deadlines
    Stein, Wei
    arXiv '23
    online
    routing / TSP
    scheduling
  • Online Time-Windows TSP with Predictions
    Chawla, Christou
    APPROX/RANDOM '24
    arXiv '23
    online
    routing / TSP
  • Mechanism Design With Predictions for Obnoxious Facility Location
    Istrate, Bonchis
    arXiv '22
    facility location
    game theory / mechanism design
  • The Safe and Effective Use of Low-Assurance Predictions in Safety-Critical Systems
    Agrawal, Baruah, Bender, Marchetti-Spaccamela
    ECRTS '23
    real-time
    scheduling
  • Competitive Search in the Line and the Star with Predictions
    Angelopoulos
    arXiv '23
    MFCS '23
    online
    search
  • Renyi-Ulam Games and Online Computation with Imperfect Advice
    Angelopoulos, Kamali
    arXiv '23
    MFCS '23
    auctions
    online
    packing
    search
  • Mixing predictions for online metric algorithms
    Antoniadis, Coester, Eliáš, Polak, Simon
    arXiv '23
    ICML '23
    k-server / MTS
    multiple predictions
    online
  • Discrete-Smoothness in Online Algorithms with Predictions
    Azar, Panigrahi, Touitou
    NeurIPS '23
    covering
    online
  • Sorting with Predictions
    Bai, Coester
    arXiv '23
    NeurIPS '23
    running time
    sorting
  • Bicriteria Multidimensional Mechanism Design with Side Information
    Balcan, Prasad, Sandholm
    arXiv '23
    NeurIPS '23
    game theory / mechanism design
  • Mechanism Design with Predictions: An Annotated Reading List
    Balkanski, Gkatzelis, Tan
    SIGecom Exch. '23
    game theory / mechanism design
    survey
  • Energy-Efficient Scheduling with Predictions
    Balkanski, Perivier, Stein, Wei
    arXiv '24
    NeurIPS '23
    online
    scheduling
  • Learning-Augmented Online TSP on Rings, Trees, Flowers and (almost) Everywhere Else
    Bampis, Escoffier, Gouleakis, Hahn, Lakis, Shahkarami, Xefteris
    arXiv '23
    ESA '23
    online
    routing / TSP
  • Graph Searching with Predictions
    Banerjee, Cohen-Addad, Gupta, Li
    arXiv '22
    ITCS '23
    exploration
    online
    search
  • Advice Querying under Budget Constraint for Online Algorithms
    Benomar, Perchet
    NeurIPS '23
    online
    parsimonious / succinct
    rent-or-buy
    scheduling
    secretary
  • Online Minimum Spanning Trees with Weight Predictions
    Berg, Boyar, Favrholdt, Larsen
    arXiv '23
    WADS '23
    network design
    online
  • Online Interval Scheduling with Predictions
    Boyar, Favrholdt, Kamali, Larsen
    arXiv '23
    WADS '23
    allocation / matching
    online
    scheduling
  • LearnedSort as a learning-augmented SampleSort: Analysis and Parallelization
    Carvalho, Lawrence
    arXiv '23
    SSDBM '23
    running time
    sorting
  • Active causal structure learning with advice
    Choo, Gouleakis, Bhattacharyya
    arXiv '23
    ICML '23
    learning
  • Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems
    Christianson, Shen, Wierman
    AISTATS '23
    k-server / MTS
    online
  • A General Framework for Learning-Augmented Online Allocation
    Cohen, Panigrahi
    arXiv '23
    ICALP '23
    allocation / matching
    online
    scheduling
  • Predictive Flows for Faster Ford-Fulkerson
    Davies, Moseley, Vassilvitskii, Wang
    arXiv '23
    ICML '23
    graph problems
    running time
  • Online Algorithms with Costly Predictions
    Drygala, Nagarajan, Svensson
    AISTATS '23
    online
    rent-or-buy
  • Trade-off Analysis in Learning-augmented Algorithms with Societal Design Criteria
    Hajiesmaili
    SIGMETRICS Perform. Evaluation Rev. '23
    online
    packing
  • Online Dynamic Acknowledgement with Learned Predictions
    Im, Moseley, Xu, Zhang
    arXiv '23
    INFOCOM '23
    online
  • Online State Exploration: Competitive Worst Case and Learning-Augmented Algorithms
    Im, Moseley, Xu, Zhang
    ECML/PKDD '23
    exploration
    online
    search
  • Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints
    Lassota, Lindermayr, Megow, Schlöter
    arXiv '23
    ICML '23
    online
    parsimonious / succinct
    scheduling
  • Speeding Up Bellman Ford via Minimum Violation Permutations
    Lattanzi, Svensson, Vassilvitskii
    ICML '23
    graph problems
    running time
    shortest path
  • Beyond Black-Box Advice: Learning-Augmented Algorithms for MDPs with Q-Value Predictions
    Li, Lin, Ren, Wierman
    arXiv '23
    NeurIPS '23
    MDP
    online
  • Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary
    Lindermayr, Megow, Rapp
    arXiv '23
    ICML '23
    online
    scheduling
  • Applied Online Algorithms with Heterogeneous Predictors
    Maghakian, Lee, Hajiesmaili, Li, Sitaraman, Liu
    ICML '23
    multiple predictions
    online
    rent-or-buy
  • Online List Labeling with Predictions
    McCauley, Moseley, Niaparast, Singh
    arXiv '23
    NeurIPS '23
    dynamic / data structure
    list labeling
  • Faster Discrete Convex Function Minimization with Predictions: The M-Convex Case
    Oki, Sakaue
    arXiv '23
    NeurIPS '23
    running time
  • Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster L-/L-Convex Function Minimization
    Sakaue, Oki
    arXiv '23
    ICML '23
    running time
  • Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis
    Shin, Lee, Lee, An
    arXiv '23
    ICML '23
    online
    rent-or-buy
  • Improved Frequency Estimation Algorithms with and without Predictions
    Aamand, Chen, Nguyen, Silwal, Vakilian
    arXiv '23
    NeurIPS '23
    parsimonious / succinct
    streaming
  • Learned Interpolation for Better Streaming Quantile Approximation with Worst Case Guarantees
    Schiefer, Chen, Indyk, Narayanan, Silwal, Wagner
    ACDA '23
    arXiv '23
    streaming
  • KwikBucks: Correlation Clustering with Cheap-Weak and Expensive-Strong Signals
    Silwal, Ahmadian, Nystrom, McCallum, Ramachandran, Kazemi
    ICLR '23
    SustaiNLP '23
    clustering
    running time
    two-oracle
  • Scheduling with Predictions
    Cho, Henderson, Shmoys
    arXiv '22
    online
    scheduling
  • Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets
    Lee, Sun, Hajiesmaili, Lui
    arXiv '22
    e-Energy '24
    online
    search
  • Improved Learning-augmented Algorithms for k-means and k-medians Clustering
    Thy Nguyen, Anamay Chaturvedi, Huy Nguyen
    arXiv '22
    ICLR '23
    approximation
    clustering
  • On the Power of Learning-Augmented BSTs
    Chen, Chen
    arXiv '22
    dynamic / data structure
    search
  • Paging with Succinct Predictions
    Antoniadis, Boyar, Eliáš, Favrholdt, Hoeksma, Larsen, Polak, Simon
    arXiv '22
    ICML '23
    caching / paging
    online
  • Proportionally Fair Online Allocation of Public Goods with Predictions
    Banerjee, Gkatzelis, Hossain, Jin, Micha, Shah
    arXiv '22
    IJCAI '23
    allocation / matching
    online
  • Private Algorithms with Private Predictions
    Amin, Dick, Khodak, Vassilvitskii
    arXiv '22
    differential privacy
  • Strategyproof Scheduling with Predictions
    Balkanski, Gkatzelis, Tan
    arXiv '22
    ITCS '23
    game theory / mechanism design
    scheduling
  • Learning-Augmented Maximum Flow
    Polak, Zub
    arXiv '22
    Inf. Process. Lett. '24
    IPL '24
    graph problems
    running time
  • Online Prediction in Sub-linear Space
    Peng, Zhang
    arXiv '22
    SODA '23
    learning
    online
  • Online TSP with Predictions
    Hu, Wei, Li, Chung, Liao
    arXiv '22
    online
    routing / TSP
  • Learning-Augmented Algorithms for Online TSP on the Line
    Gouleakis, Lakis, Shahkarami
    AAAI '23
    arXiv '22
    online
    routing / TSP
  • On Preemption and Learning in Stochastic Scheduling
    Merlis, Richard, Sentenac, Odic, Molina, Perchet
    arXiv '22
    ICML '23
    learning
    scheduling
  • Scheduling with Speed Predictions
    Balkanski, Ou, Stein, Wei
    arXiv '22
    WAOA '23
    online
    scheduling
  • Single-Leg Revenue Management with Advice
    Balseiro, Kroer, Kumar
    arXiv '22
    EC '23
    online
  • Lazy Lagrangians with Predictions for Online Learning
    Anderson, Iosifidis, Leith
    arXiv '22
    learning
    online
  • Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location
    Agrawal, Balkanski, Gkatzelis, Ou, Tan
    arXiv '22
    EC '22
    game theory / mechanism design
    network design
  • Online Algorithms with Multiple Predictions
    Anand, Ge, Kumar, Panigrahi
    arXiv '22
    ICML '22
    covering
    multiple predictions
    online
  • A Novel Prediction Setup for Online Speed-Scaling
    Antoniadis, Ganje, Shahkarami
    arXiv '21
    SWAT '22
    online
    scheduling
  • Online Graph Algorithms with Predictions
    Azar, Panigrahi, Touitou
    arXiv '21
    SODA '22
    network design
    online
  • Distortion-Oblivious Algorithms for Scheduling on Multiple Machines
    Azar, Peretz, Touitou
    ISAAC '22
    online
    scheduling
  • Scheduling with Untrusted Predictions
    Bampis, Dogeas, Kononov, Lucarelli, Pascual
    IJCAI '22
    online
    scheduling
  • Canadian Traveller Problem with Predictions
    Bampis, Escoffier, Xefteris
    arXiv '22
    WAOA '22
    online
    routing / TSP
  • A Universal Error Measure for Input Predictions Applied to Online Graph Problems
    Bernardini, Lindermayr, Marchetti-Spaccamela, Megow, Stougie, Sweering
    arXiv '22
    NeurIPS '22
    network design
    online
    routing / TSP
  • Machine Learning Advised Ski Rental Problem with a Discount
    Bhattacharya, Das
    WALCOM '22
    online
    rent-or-buy
  • Online Unit Profit Knapsack with Untrusted Predictions
    Boyar, Favrholdt, Larsen
    arXiv '22
    SWAT '22
    online
    packing
  • Triangle and Four Cycle Counting with Predictions in Graph Streams
    Chen, Eden, Indyk, Lin, Narayanan, Rubinfeld, Silwal, Wagner, Woodruff, Zhang
    arXiv '22
    ICLR '22
    streaming
  • Faster Fundamental Graph Algorithms via Learned Predictions
    Chen, Silwal, Vakilian, Zhang
    arXiv '22
    ICML '22
    allocation / matching
    running time
    shortest path
  • Chasing Convex Bodies and Functions with Black-Box Advice
    Christianson, Handina, Wierman
    arXiv '22
    COLT '22
    convex body chasing
    online
  • Algorithms with Prediction Portfolios
    Dinitz, Im, Lavastida, Moseley, Vassilvitskii
    arXiv '22
    NeurIPS '22
    allocation / matching
    multiple predictions
    online
    scheduling
  • Robustification of Online Graph Exploration Methods
    Eberle, Lindermayr, Megow, Nölke, Schlöter
    AAAI '22
    arXiv '21
    exploration
    online
    search
  • Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty
    Erlebach, Lima, Megow, Schlöter
    arXiv '22
    ESA '22
    explorable uncertainty
    network design
    online
  • Approximate Cluster Recovery from Noisy Labels
    Gamlath, Lattanzi, Norouzi-Fard, Svensson
    COLT '22
    approximation
    clustering
  • Improved Price of Anarchy via Predictions
    Gkatzelis, Kollias, Sgouritsa, Tan
    arXiv '22
    EC '22
    game theory / mechanism design
  • Learning-Augmented Algorithms for Online Linear and Semidefinite Programming
    Grigorescu, Lin, Silwal, Song, Zhou
    arXiv '22
    NeurIPS '22
    covering
    online
    SDP
  • Parsimonious Learning-Augmented Caching
    Im, Kumar, Petety, Purohit
    arXiv '22
    ICML '22
    caching / paging
    online
  • Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model
    Jin, Ma
    arXiv '22
    NeurIPS '22
    allocation / matching
    online
  • Learning Predictions for Algorithms with Predictions
    Khodak, Balcan, Talwalkar, Vassilvitskii
    arXiv '22
    NeurIPS '22
    learning
    online
  • Offline and Online Algorithms for SSD Management
    Lange, Naor, Yadgar
    CACM '23
    SIGMETRICS '22
    online
    scheduling
  • Learning-Augmented Binary Search Trees
    Lin, Luo, Woodruff
    arXiv '22
    ICML '22
    dynamic / data structure
    search
  • Permutation Predictions for Non-Clairvoyant Scheduling
    Lindermayr, Megow
    arXiv '22
    SPAA '22
    online
    parsimonious / succinct
    scheduling
  • Robust Load Balancing with Machine Learned Advice
    Peng, Ahmadian, Esfandiari, Mirrokni
    J. Mach. Learn. Res. '23
    SODA '22
    allocation / matching
    online
    scheduling
  • Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions
    Sakaue, Oki
    arXiv '22
    NeurIPS '22
    allocation / matching
    matroid
    running time
  • Mechanism Design with Predictions
    Xu, Lu
    arXiv '22
    IJCAI '22
    auctions
    game theory / mechanism design
    scheduling
  • Learning-Augmented Algorithms for Online Steiner Tree
    Xu, Moseley
    AAAI '22
    arXiv '21
    network design
    online
  • Learning-augmented algorithms for online subset sum
    Xu, Zhang
    J. Glob. Optim. '23
    J. Global Optimization '22
    covering
    online
  • Brief Announcement: Towards a More Robust Algorithm for Flow Time Scheduling with Predictions
    Zhao, Li, Li, Zomaya
    SPAA '22
    online
    scheduling
  • Uniform Machine Scheduling with Predictions
    Zhao, Li, Zomaya
    ICAPS '22
    online
    scheduling
  • Real-Time Scheduling with Predictions
    Zhao, Li, Zomaya
    RTSS '22
    online
    scheduling
  • Using Machine Learning Predictions to Speed-up Dijkstra's Shortest Path Algorithm
    Feijen, Schäfer
    arXiv '21
    running time
    shortest path
  • Competitive Sequencing with Noisy Advice
    Angelopoulos, Kamali, Shadkami
    arXiv '21
    online
    scheduling
  • Learning-Augmented k-means Clustering
    Ergun, Feng, Silwal, Woodruff, Zhou
    arXiv '21
    ICLR '22
    approximation
    clustering
    running time
  • Online Facility Location with Predictions
    Jiang, Liu, Lyu, Tang, Zhang
    arXiv '21
    ICLR '22
    network design
    online
  • Online Primal-Dual Algorithms with Predictions for Packing Problems
    Dürr, Thang
    arXiv '21
    online
    packing
  • Uniform Bounds for Scheduling with Job Size Estimates
    Scully, Grosof, Mitzenmacher
    arXiv '21
    ITCS '22
    online
    queueing
  • Can Q-Learning be Improved with Advice?
    Golowich, Moitra
    arXiv '21
    COLT '22
    learning
  • Distortion-Oblivious Algorithms for Minimizing Flow Time
    Azar, Leonardi, Touitou
    arXiv '21
    SODA '22
    online
    scheduling
  • Learning to Hash Robustly, Guaranteed
    Andoni, Beaglehole
    arXiv '21
    ICML '22
    hashing
    running time
  • Optimal Stopping Methodology for the Secretary Problem with Random Queries
    Moustakides, Liu, Milenkovic
    arXiv '21
    J. Appl. Probab. '24
    exploration
    online
    secretary
  • Learning Augmented Online Facility Location
    Fotakis, Gergatsouli, Gouleakis, Patris
    arXiv '21
    facility location
    online
  • Robustness and Consistency in Linear Quadratic Control with Untrusted Predictions
    Li, Yang, Qu, Shi, Yu, Wierman, Low
    arXiv '21
    Proc. ACM Meas. Anal. Comput. Syst. '22
    SIGMETRICS '22
    linear quadratic control
    online
  • Double Coverage with Machine-Learned Advice
    Lindermayr, Megow, Simon
    arXiv '21
    ITCS '22
    k-server / MTS
    online
  • Online Bin Packing with Predictions
    Angelopoulos, Kamali, Shadkami
    arXiv '21
    IJCAI '22
    J. Artif. Intell. Res. '23
    online
    packing
  • Online Bipartite Matching with Predicted Degrees
    Aamand, Chen, Indyk
    arXiv '21
    allocation / matching
    online
  • Online Facility Location with Multiple Advice
    Almanza, Chierichetti, Lattanzi, Panconesi, Re
    NeurIPS '21
    network design
    online
  • A Regression Approach to Learning-Augmented Online Algorithms
    Anand, Ge, Kumar, Panigrahi
    arXiv '22
    NeurIPS '21
    learning
    online
  • Learning-Augmented Dynamic Power Management with Multiple States via New Ski-Rental Bounds
    Antoniadis, Coester, Elias, Polak, Simon
    arXiv '21
    NeurIPS '21
    online
    rent-or-buy
  • Flow Time Scheduling with Uncertain Processing Time
    Azar, Leonardi, Touitou
    arXiv '21
    STOC '21
    online
    scheduling
  • Logarithmic Regret from Sublinear Hints
    Bhaskara, Cutkosky, Kumar, Purohit
    arXiv '21
    NeurIPS '21
    learning
    online
  • A learned approach to design compressed rank/select data structures
    Boffa, Ferragina, Vinciguerra
    ACM Trans. Algorithms '22
    ALENEX '21
    TALG '22
    dynamic / data structure
  • Robust Learning-Augmented Caching: An Experimental Study
    Chłędowski, Polak, Szabucki, Żołna
    arXiv '21
    ICML '21
    caching / paging
    online
  • Learning Online Algorithms with Distributional Advice
    Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, Nikos Zarifis
    ICML '21
    learning
    online
    rent-or-buy
  • Faster Matchings via Learned Duals
    Dinitz, Im, Lavastida, Moseley, Vassilvitskii
    arXiv '21
    NeurIPS '21
    allocation / matching
    running time
  • Putting the \"Learning\" into Learning-Augmented Algorithms for Frequency Estimation
    Du, Wang, Mitzenmacher
    ICML '21
    learning
    streaming
  • Learning-based support estimation in sublinear time
    Eden, Indyk, Narayanan, Rubinfeld, Silwal, Wagner
    arXiv '21
    ICLR '21
    running time
    sample complexity
  • On the performance of learned data structures
    Ferragina, Lillo, Vinciguerra
    Theor. Comput. Sci. '21
    dynamic / data structure
  • Repetition- and Linearity-Aware Rank/Select Dictionaries
    Ferragina, Manzini, Vinciguerra
    ISAAC '21
    dynamic / data structure
  • Non-Clairvoyant Scheduling with Predictions
    Im, Kumar, Quaem, Purohit
    ACM Trans. Parallel Comput. '23
    ISAIM '22
    SPAA '21
    online
    scheduling
  • Online Knapsack with Frequency Predictions
    Im, Kumar, Quaem, Purohit
    NeurIPS '21
    online
    packing
  • Using Predicted Weights for Ad Delivery
    Lavastida, Moseley, Ravi, Xu
    ACDA '21
    arXiv '21
    allocation / matching
    online
  • Online peak-aware energy scheduling with untrusted advice
    Lee, Maghakian, Hajiesmaili, Sitaraman, Liu
    e-Energy '21
    SIGENERGY '22
    online
    scheduling
  • Online Unrelated Machine Load Balancing with Predictions Revisited
    Li, Xian
    ICML '21
    online
    scheduling
  • A New Approach to Capacity Scaling Augmented With Unreliable Machine Learning Predictions
    Rutten, Mukherjee
    arXiv '21
    Math. Oper. Res. '24
    online
    scheduling
  • Pareto-optimal learning-augmented algorithms for online conversion problems
    Sun, Lee, Hajiesmaili, Wierman, Tsang
    arXiv '21
    NeurIPS '21
    online
  • Data-driven Competitive Algorithms for Online Knapsack and Set Cover
    Zeynali, Sun, Hajiesmaili, Wierman
    AAAI '21
    arXiv '20
    covering
    learning
    online
    packing
  • Prediction Augmented Segment Routing
    Kodialam, Lakshman
    HPSR '21
    online
    routing / TSP
  • Contract scheduling with predictions
    Angelopoulos, Kamali
    AAAI '21
    arXiv '20
    J. Artif. Intell. Res. '23
    online
    scheduling
  • Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing
    Lavastida, Moseley, Ravi, Xu
    arXiv '20
    ESA '21
    allocation / matching
    online
    scheduling
  • Learning-Augmented Weighted Paging
    Bansal, Coester, Kumar, Purohit, Vee
    arXiv '20
    SODA '22
    caching / paging
    online
  • Online Paging with a Vanishing Regret
    Emek, Kutten, Shi
    arXiv '20
    ITCS '21
    caching / paging
    online
  • Secretaries with Advice
    Düttung, Lattanzi, Leme, Vassilvitskii
    arXiv '20
    EC '21
    Math. Oper. Res. '24
    online
    secretary
  • Generalized Sorting with Predictions
    Lu, Ren, Sun, Zhang
    arXiv '20
    SOSA '21
    running time
    sorting
  • Online Search With a Hint
    Angelopoulos
    arXiv '20
    Inf. Comput. '23
    ITCS '21
    online
    search
  • Online Nash Social Welfare Maximization with Predictions
    Banerjee, Gkatzelis, Gorokh, Jin
    arXiv '20
    SODA '22
    online
  • Queues with Small Advice
    Mitzenmacher
    ACDA '21
    arXiv '20
    online
    queueing
  • Online Page Migration with ML Advice
    Indyk, Mallmann-Trenn, Mitrovic, Rubinfeld
    AISTATS '22
    arXiv '20
    caching / paging
    online
  • Customizing ML Predictions For Online Algorithms
    Anand, Ge, Panigrahi
    arXiv '22
    ICML '20
    learning
    online
    rent-or-buy
  • Online metric algorithms with untrusted predictions
    Antoniadis, Coester, Elias, Polak, Simon
    ACM Trans. Algorithms '23
    arXiv '20
    ICML '20
    allocation / matching
    caching / paging
    k-server / MTS
    online
  • Secretary and Online Matching Problems with Machine Learned Advice
    Antoniadis, Gouleakis, Kleer, Kolev
    arXiv '20
    NeurIPS '20
    allocation / matching
    online
    secretary
  • Learning Augmented Energy Minimization via Speed Scaling
    Bamas, Maggiori, Rohwedder, Svensson
    arXiv '20
    NeurIPS '20
    online
    scheduling
  • The Primal-Dual method for Learning Augmented Algorithms
    Bamas, Maggiori, Svensson
    arXiv '20
    NeurIPS '20
    covering
    online
    rent-or-buy
  • Improving Online Rent-or-Buy Algorithms with Sequential Decision Making and ML Predictions
    Banerjee
    NeurIPS '20
    online
    rent-or-buy
  • Untrusted Predictions Improve Trustable Query Policies
    Erlebach, Hoffmann, de Lima, Megow, Schlöter
    arXiv '20
    explorable uncertainty
    online
  • The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds
    Ferragina, Vinciguerra
    Proc. VLDB Endow. '20
    dynamic / data structure
  • Learning-augmented data stream algorithms
    Jiang, Li, Lin, Ruan, Woodruff
    ICLR '20
    streaming
  • Online Algorithms for Weighted Paging with Predictions
    Jiang, Panigrahi, Su
    ACM Trans. Algorithms '22
    arXiv '20
    ICALP '20
    caching / paging
    online
  • Algorithms with Predictions
    Mitzenmacher, Vassilvitskii
    arXiv '20
    Beyond the Worst-Case Analysis of Algorithms '20
    Commun. ACM '22
    survey
  • Online scheduling via learned weights
    Moseley, Vassilvitskii, Lattanzi, Lavastida
    SODA '20
    online
    scheduling
  • Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice
    Wang, Li, Wang
    arXiv '20
    NeurIPS '20
    online
    rent-or-buy
  • Better and simpler learning-augmented online caching
    Wei
    APPROX-RANDOM '20
    arXiv '20
    caching / paging
    online
  • Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms
    Wei, Zhang
    arXiv '20
    NeurIPS '20
    online
    rent-or-buy
    scheduling
  • Near-optimal bounds for online caching with machine learned advice
    Rohatgi
    arXiv '19
    SODA '20
    caching / paging
    online
  • (Learned) Frequency Estimation Algorithms under Zipfian Distribution
    Aamand, Indyk, Vakilian
    arXiv '19
    streaming
  • The Supermarket Model with Known and Predicted Service Times
    Mitzenmacher, Dell Amico
    arXiv '19
    IEEE Trans. Parallel Distributed Syst. '22
  • Online Computation with Untrusted Advice
    Angelopoulos, Dürr, Jin, Kamali, Renault
    arXiv '19
    ITCS '20
    J. Comput. Syst. Sci. '24
    online
    packing
    rent-or-buy
  • Scheduling with Predictions and the Price of Misprediction
    Mitzenmacher
    arXiv '19
    ITCS '20
    online
    queueing
  • Learned data structures
    Ferragina, Vinciguerra
    INNSBDDL '19
    dynamic / data structure
  • Online algorithms for rent-or-buy with expert advice
    Gollapudi, Panigrahi
    ICML '19
    online
    rent-or-buy
  • Learning-Based Frequency Estimation Algorithms
    Hsu, Indyk, Katabi, Vakilian
    ICLR '19
    streaming
  • Learning-Based Low-Rank Approximations
    Indyk, Vakilian, Yuan
    arXiv '19
    NeurIPS '19
  • The Case for Learned Index Structures
    Kraska, Beutel, Chi, Dean, Polyzotis
    arXiv '17
    SIGMOD Conference '18
    dynamic / data structure
  • Competitive Caching with Machine Learned Advice
    Lykouris, Vassilvitskii
    arXiv '18
    ICML '18
    J. ACM '21
    caching / paging
    online
  • A model for learned bloom filters and optimizing by sandwiching
    Mitzenmacher
    arXiv '19
    NeurIPS '18
  • Improving online algorithms via ML predictions
    Purohit, Svitkina, Kumar
    arXiv '24
    NeurIPS '18
    online
    rent-or-buy
    scheduling
  • Revenue optimization with approximate bid predictions
    Medina, Vassilvitskii
    arXiv '17
    NIPS '17
    prior/related work
  • Optimal online assignment with forecasts
    Vee, Vassilvitskii, Shanmugasundaram
    EC '10
    prior/related work
  • The adwords problem: online keyword matching with budgeted bidders under random permutations
    Devanur, Hayes
    EC '09
    prior/related work
  • Allocating online advertisement space with unreliable estimates
    Mahdian, Nazerzadeh, Saberi
    EC '07
    matching / allocation
    online

dynamic / data structure
online
running time
approximation
streaming
game theory / mechanism design
differential privacy
survey
prior/related work

allocation / matching
auctions
caching / paging
clustering
convex body chasing
covering
distributed algorithms
explorable uncertainty
exploration
facility location
graph problems
hashing
k-server / MTS
learning
linear quadratic control
list labeling
matching / allocation
matroid
MDP
multiple predictions
network design
networks
packing
parsimonious / succinct
queueing
real-time
rent-or-buy
robustness
routing / TSP
sample complexity
scheduling
SDP
search
secretary
shortest path
sorting
submodular maximization
two-oracle