ALPS

225 papers


  • Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems
    Grigorescu, Lin, Song
    arXiv '24
    convex optimization
    online
    packing
  • Strategic Facility Location via Predictions
    Chen, Gravin, Im
    arXiv '24
    AGT
    facility location
  • 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
    algorithmic recourse
    robustness
  • The Secretary Problem with Predicted Additive Gap
    Braun, Sarkar
    arXiv '24
    online
    secretary
  • 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
    frequency estimation
    streaming
  • Randomized Strategic Facility Location with Predictions
    Balkanski, Gkatzelis, Shahkarami
    arXiv '24
    AGT
    facility location
  • CarbonClipper: Optimal Algorithms for Carbon-Aware Spatiotemporal Workload Management
    Lechowicz, Christianson, Sun, Bashir, Hajiesmaili, Wierman, Shenoy
    arXiv '24
    allocation
    online
  • Clock Auctions Augmented with Unreliable Advice
    Gkatzelis, Schoepflin, Tan
    arXiv '24
    AGT
    auctions
  • Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms
    Angelopoulos, Dürr, Elenter, Lefki
    arXiv '24
    online
    trading
  • Complexity Classes for Online Problems with and without Predictions
    Berg, Boyar, Favrholdt, Larsen
    arXiv '24
    online
  • Mechanism Design Augmented with Output Advice
    Christodoulou, Sgouritsa, Vlachos
    arXiv '24
    AGT
    auctions
    facility location
    mechanism design
    scheduling
  • Learning-Augmented Priority Queues
    Benomar, Coester
    arXiv '24
    data structure
    priority queue
  • A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives
    Grigorescu, Lin, Song
    arXiv '24
    knapsack
    online
    packing
    scheduling
  • Warm-starting Push-Relabel
    Davies, Vassilvitskii, Wang
    arXiv '24
    max flow
    running time
  • Online Classification with Predictions
    Raman, Tewari
    arXiv '24
    learning
    online
  • Equilibria in multiagent online problems with predictions
    Istrate, Bonchis, Bogdan
    arXiv '24
    AGT
    multiagent
    online
    rent-or-buy
  • Online Lead Time Quotation with Predictions
    Huo, Tianming; Cheung, Wang Chi
    SSRN '24
    competitive analysis
    lead time quotation
    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
    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
    caching
    load balancing
    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
    AGT
    assignment problem
    graph problems
  • Best of Many in Both Worlds: Online Resource Allocation with Predictions under Unknown Arrival Model
    An, Li, Moseley, Visotsky
    arXiv '24
    allocation
    online
  • Learning-Augmented Skip Lists
    Fu, Seo, Zhou
    arXiv '24
    data structure
    dictionary
    search
  • Max-Cut with ε-Accurate Predictions
    Cohen-Addad, d'Orsi, Gupta, Lee, Panigrahi
    arXiv '24
    approximation
    max-cut
  • Online Covering with Multiple Experts
    Kevi, Nguyen
    arXiv '23
    covering problems
    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
    buffer sharing
    communication networks
    online
    queueing
  • Online Graph Coloring with Predictions
    Antoniadis, Broersma, Meng
    arXiv '23
    ISCO '24
    graph coloring
    online
  • 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
    AGT
    facility location
    mechanism design
  • Online Bin Covering with Frequency Predictions
    Berg, Kamali
    arXiv '24
    SWAT '24
    covering problems
    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
    AGT
    auctions
    mechanism design
  • Online bipartite matching with imperfect advice
    Choo, Gouleakis, Ling, Bhattacharyya
    arXiv '24
    ICML '24
    allocation
    matching
    online
  • 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
    knapsack
    online
  • Connectivity Oracles for Predictable Vertex Failures
    Hu, Kosinas, Polak
    arXiv '23
    ESA '24
    connectivity oracle
    data structure
  • Chasing Convex Functions with Long-term Constraints
    Lechowicz, Christianson, Sun, Bashir, Hajiesmaili, Wierman, Shenoy
    arXiv '24
    ICML '24
    convex optimization
    MTS
    online
    search
  • Incremental Topological Ordering and Cycle Detection with Predictions
    McCauley, Moseley, Niaparast, Singh
    arXiv '24
    ICML '24
    data structure
    graph algorithms
    running time
  • Algorithms for Caching and MTS with Reduced Number of Predictions
    Sadek, Elias
    arXiv '24
    ICLR '24
    caching/paging
    MTS
    online
  • Robust Learning-Augmented Dictionaries
    Zeynali, Kamali, Hajiesmaili
    arXiv '24
    ICML '24
    data structure
    dictionary
    search
  • Cost-Driven Data Replication with Predictions
    Zuo, Tang, Lee
    arXiv '24
    SPAA '24
    data replication
    online
  • Learning-Augmented Algorithms for the Bahncard Problem
    Zhao, Tang, Chen, Deng
    arXiv '24
    NeurIPS '24
    Bahncard
    rent-or-buy
  • Learning-Augmented Dynamic Submodular Maximization
    Agarwal, Balkanski
    arXiv '23
    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
    convex optimization
    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
    AGT
    auctions
    mechanism design
  • Competitive Auctions with Imperfect Predictions
    Lu, Wan, Zhang
    arXiv '23
    AGT
    auctions
  • On the Complexity of Algorithms with Predictions for Dynamic Graph Problems
    Henzinger, Lincoln, Saha, Seybold, Ye
    arXiv '23
    ITCS '24
    data structure
    running time
  • On Dynamic Graph Algorithms with Predictions
    Brand, Forster, Nazari, Polak
    arXiv '23
    SODA '24
    data structure
    graph algorithms
    running time
  • Online Resource Allocation with Convex-set Machine-Learned Advice
    Golrezaei, Jaillet, Zhou
    arXiv '23
    allocation
    online
  • The Predicted-Deletion Dynamic Model: Taking Advantage of ML Predictions, for Free
    Liu, Srinivas
    arXiv '23
    data structure
    running time
  • Learning-Augmented Decentralized Online Convex Optimization in Networks
    Li, Yang, Wierman, Ren
    arXiv '23
    convex optimization
    online
  • Optimal Metric Distortion with Predictions
    Berger, Feldman, Gkatzelis, Tan
    arXiv '23
    AGT
    metric distortion
  • 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
    fairness
    knapsack
    online
    packing
  • The Nonstationary Newsvendor with (and without) Predictions
    An, Li, Moseley, Ravi
    arXiv '23
    newsvendor
    online
    regret analysis
  • Learning-Augmented Online Packet Scheduling with Deadlines
    Stein, Wei
    arXiv '23
    online
    routing
    scheduling
  • Online Time-Windows TSP with Predictions
    Chawla, Christou
    APPROX/RANDOM '24
    arXiv '23
    online
    routing
  • Mechanism Design With Predictions for Obnoxious Facility Location
    Istrate, Bonchis
    arXiv '22
    AGT
    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
    MTS
    multiple predictions
    online
  • Discrete-Smoothness in Online Algorithms with Predictions
    Azar, Panigrahi, Touitou
    NeurIPS '23
    covering problems
    online
    set cover
  • 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
    AGT
    mechanism design
  • 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
  • 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
    rent/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
    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
    causal structure learning
    causality
  • Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems
    Christianson, Shen, Wierman
    AISTATS '23
    MTS
    online
  • A General Framework for Learning-Augmented Online Allocation
    Cohen, Panigrahi
    arXiv '23
    ICALP '23
    allocation
    online
    scheduling
  • Predictive Flows for Faster Ford-Fulkerson
    Davies, Moseley, Vassilvitskii, Wang
    arXiv '23
    ICML '23
    max flow
    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
    knapsack
    online
  • Online Dynamic Acknowledgement with Learned Predictions
    Im, Moseley, Xu, Zhang
    arXiv '23
    INFOCOM '23
    dynamic acknowledgement
    online
  • Online State Exploration: Competitive Worst Case and Learning-Augmented Algorithms
    Im, Moseley, Xu, Zhang
    ECML/PKDD '23
    bidding
    online
    search
    state exploration
  • Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints
    Lassota, Lindermayr, Megow, Schlöter
    arXiv '23
    ICML '23
    online
    scheduling
  • Speeding Up Bellman Ford via Minimum Violation Permutations
    Lattanzi, Svensson, Vassilvitskii
    ICML '23
    graph algorithms
    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/buy
  • Online List Labeling with Predictions
    McCauley, Moseley, Niaparast, Singh
    arXiv '23
    NeurIPS '23
    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
    count sketch
    frequency estimation
    parsimonious
    streaming algorithms
    sublinear algorithms
  • Learned Interpolation for Better Streaming Quantile Approximation with Worst Case Guarantees
    Schiefer, Chen, Indyk, Narayanan, Silwal, Wagner
    ACDA '23
    arXiv '23
    quantiles
    streaming algorithms
    sublinear algorithms
  • KwikBucks: Correlation Clustering with Cheap-Weak and Expensive-Strong Signals
    Silwal, Ahmadian, Nystrom, McCallum, Ramachandran, Kazemi
    ICLR '23
    SustaiNLP '23
    clustering
    correlation clustering
    large language models
    query complexity
    weak and strong signals
  • 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
    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
    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
    AGT
    scheduling
  • Learning-Augmented Maximum Flow
    Polak, Zub
    arXiv '22
    Inf. Process. Lett. '24
    IPL '24
    max flow
    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
  • Learning-Augmented Algorithms for Online TSP on the Line
    Gouleakis, Lakis, Shahkarami
    AAAI '23
    arXiv '22
    online
    routing
  • 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
  • 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
    AGT
    network design
  • Online Algorithms with Multiple Predictions
    Anand, Ge, Kumar, Panigrahi
    arXiv '22
    ICML '22
    cover problems
    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
  • 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
  • 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
    subgraph counting
    sublinear algorithms
  • Faster Fundamental Graph Algorithms via Learned Predictions
    Chen, Silwal, Vakilian, Zhang
    arXiv '22
    ICML '22
    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
    load balancing
    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
    AGT
  • Learning-Augmented Algorithms for Online Linear and Semidefinite Programming
    Grigorescu, Lin, Silwal, Song, Zhou
    arXiv '22
    NeurIPS '22
    covering problems
    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
    matching
    online
  • Learning Predictions for Algorithms with Predictions
    Khodak, Balcan, Talwalkar, Vassilvitskii
    arXiv '22
    NeurIPS '22
    learning
    online
  • Learning-Augmented Binary Search Trees
    Lin, Luo, Woodruff
    arXiv '22
    ICML '22
    data structure
    search
  • Permutation Predictions for Non-Clairvoyant Scheduling
    Lindermayr, Megow
    arXiv '22
    SPAA '22
    online
    scheduling
  • Robust Load Balancing with Machine Learned Advice
    Peng, Ahmadian, Esfandiari, Mirrokni
    J. Mach. Learn. Res. '23
    SODA '22
    load balancing
    online
    scheduling
  • Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions
    Sakaue, Oki
    arXiv '22
    NeurIPS '22
    matching
    matroid intersection
    running time
  • Mechanism Design with Predictions
    Xu, Lu
    arXiv '22
    IJCAI '22
    AGT
    auctions
    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
    online
    subset sum
  • 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
    beyond NP hardness
    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
    locality sensitive hashing
    nearest neighbors search
    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
    network design
    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
    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
    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
    data structure
  • Robust Learning-Augmented Caching: An Experimental Study
    Chłędowski, Polak, Szabucki, Żołna
    arXiv '21
    ICML '21
    caching/paging
    experiments
    online
  • Learning Online Algorithms with Distributional Advice
    Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, Nikos Zarifis
    ICML '21
    learning
    online
    prophet
    rent-or-buy
  • Faster Matchings via Learned Duals
    Dinitz, Im, Lavastida, Moseley, Vassilvitskii
    arXiv '21
    NeurIPS '21
    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
    sublinear algorithms
  • On the performance of learned data structures
    Ferragina, Lillo, Vinciguerra
    Theor. Comput. Sci. '21
    data structure
  • Repetition- and Linearity-Aware Rank/Select Dictionaries
    Ferragina, Manzini, Vinciguerra
    ISAAC '21
    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
    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
    data-driven
    learning
    online
    packing
    set cover
  • Prediction Augmented Segment Routing
    Kodialam, Lakshman
    HPSR '21
    online
    routing
  • 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
    online
    page migration
  • 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
    caching/paging
    k-server
    matching
    MTS
    online
  • Secretary and Online Matching Problems with Machine Learned Advice
    Antoniadis, Gouleakis, Kleer, Kolev
    arXiv '20
    NeurIPS '20
    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
    online
    rent-or-buy
    set cover
  • 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
    online
  • The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds
    Ferragina, Vinciguerra
    Proc. VLDB Endow. '20
    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
    bidding
    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
    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
    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
    prior/related work

data structure
online
running time
approximation
AGT
differential privacy
prior/related work

algorithmic recourse
allocation
assignment problem
auctions
Bahncard
beyond NP hardness
bidding
buffer sharing
caching
caching/paging
causal structure learning
causality
clustering
communication networks
competitive analysis
connectivity oracle
convex body chasing
convex optimization
correlation clustering
count sketch
cover problems
covering problems
data replication
data-driven
dictionary
dynamic acknowledgement
experiments
explorable uncertainty
exploration
facility location
fairness
frequency estimation
graph algorithms
graph coloring
graph problems
k-server
knapsack
large language models
lead time quotation
learning
linear quadratic control
list labeling
load balancing
locality sensitive hashing
matching
matroid intersection
max flow
max-cut
MDP
mechanism design
metric distortion
MTS
multiagent
multiple predictions
nearest neighbors search
network design
newsvendor
packing
page migration
parsimonious
priority queue
prophet
quantiles
query complexity
queueing
real-time
regret analysis
rent-or-buy
rent/buy
robustness
routing
sample complexity
scheduling
SDP
search
secretary
set cover
shortest path
sorting
state exploration
streaming
streaming algorithms
subgraph counting
sublinear algorithms
submodular maximization
subset sum
survey
trading
weak and strong signals