ALPS
Algorithms with Predictions
Paper ListFurther MaterialAbout

118 papers


  • Algorithms with Prediction Portfolios
    Dinitz, Im, Lavastida, Moseley, Vassilvitskii
    arXiv '22
    load balancing
    matching
    multiple predictions
    online
    scheduling
  • Private Algorithms with Private Predictions
    Amin, Dick, Khodak, Vassilvitskii
    arXiv '22
    differential privacy
  • Paging with Succinct Predictions
    Antoniadis, Boyar, Eliáš, Favrholdt, Hoeksma, Larsen, Polak, Simon
    arXiv '22
    caching/paging
    online
  • Proportionally Fair Online Allocation of Public Goods with Predictions
    Banerjee, Gkatzelis, Hossain, Jin, Micha, Shah
    arXiv '22
    allocation
    online
  • Canadian Traveller Problem with Predictions
    Bampis, Escoffier, Xefteris
    arXiv '22
    WAOA '22
    online
    routing
  • Learning-Augmented Algorithms for Online Linear and Semidefinite Programming
    Grigorescu, Lin, Silwal, Song, Zhou
    arXiv '22
    covering problems
    online
    SDP
  • Strategyproof Scheduling with Predictions
    Balkanski, Gkatzelis, Tan
    arXiv '22
    AGT
    scheduling
  • Learning-Augmented Maximum Flow
    Polak, Zub
    arXiv '22
    max flow
    running time
  • Online Prediction in Sub-linear Space
    Peng, Zhang
    arXiv '22
    learning
    online
  • Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty
    Erlebach, Lima, Megow, Schlöter
    arXiv '22
    ESA '22
    explorable uncertainty
    network design
    online
  • Online TSP with Predictions
    Hu, Wei, Li, Chung, Liao
    arXiv '22
    online
    routing
  • Learning-Augmented Binary Search Trees
    Lin, Luo, Woodruff
    arXiv '22
    ICML '22
    data structure
    search
  • Chasing Convex Bodies and Functions with Black-Box Advice
    Christianson, Handina, Wierman
    arXiv '22
    COLT '22
    convex body chasing
    online
  • Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model
    Jin, Ma
    arXiv '22
    matching
    online
  • Learning-Augmented Algorithms for Online TSP on the Line
    Gouleakis, Lakis, Shahkarami
    arXiv '22
    online
    routing
  • A Universal Error Measure for Input Predictions Applied to Online Graph Problems
    Bernardini, Lindermayr, Marchetti-Spaccamela, Megow, Stougie, Sweering
    arXiv '22
    network design
    online
    routing
  • Mechanism Design with Predictions
    Xu, Lu
    arXiv '22
    IJCAI '22
    AGT
    auctions
    scheduling
  • Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions
    Sakaue, Oki
    arXiv '22
    matching
    matroid intersection
    running time
  • A Regression Approach to Learning-Augmented Online Algorithms
    Anand, Ge, Kumar, Panigrahi
    arXiv '22
    NeurIPS '21
    learning
    online
  • Customizing ML Predictions For Online Algorithms
    Anand, Ge, Panigrahi
    arXiv '22
    ICML '20
    learning
    online
    rent-or-buy
  • Improved Price of Anarchy via Predictions
    Gkatzelis, Kollias, Sgouritsa, Tan
    arXiv '22
    EC '22
    AGT
  • Online Algorithms with Multiple Predictions
    Anand, Ge, Kumar, Panigrahi
    arXiv '22
    ICML '22
    cover problems
    multiple predictions
    online
  • Scheduling with Speed Predictions
    Balkanski, Ou, Stein, Wei
    arXiv '22
    online
    scheduling
  • Faster Fundamental Graph Algorithms via Learned Predictions
    Chen, Silwal, Vakilian, Zhang
    arXiv '22
    ICML '22
    matching
    running time
    shortest path
  • Learning-Augmented k-means Clustering
    Ergun, Feng, Silwal, Woodruff, Zhou
    arXiv '22
    ICLR '22
    beyond NP hardness
    clustering
    running time
  • Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location
    Agrawal, Balkanski, Gkatzelis, Ou, Tan
    arXiv '22
    EC '22
    AGT
    network design
  • 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 algorithms
    subgraph counting
    sublinear algorithms
  • Online Unit Profit Knapsack with Untrusted Predictions
    Boyar, Favrholdt, Larsen
    arXiv '22
    SWAT '22
    online
    packing
  • Permutation Predictions for Non-Clairvoyant Scheduling
    Lindermayr, Megow
    arXiv '22
    SPAA '22
    online
    scheduling
  • Single-Leg Revenue Management with Advice
    Balseiro, Kroer, Kumar
    arXiv '22
  • Learning Predictions for Algorithms with Predictions
    Khodak, Balcan, Talwalkar, Vassilvitskii
    arXiv '22
    learning
    online
  • Parsimonious Learning-Augmented Caching
    Im, Kumar, Petety, Purohit
    arXiv '22
    ICML '22
    caching/paging
    online
  • Lazy Lagrangians with Predictions for Online Learning
    Anderson, Iosifidis, Leith
    arXiv '22
    learning
    online
  • Scheduling with Untrusted Predictions
    Bampis, Dogeas, Kononov, Lucarelli, Pascual
    IJCAI '22
    online
    scheduling
  • Machine Learning Advised Ski Rental Problem with a Discount
    Bhattacharya, Das
    WALCOM '22
    online
    rent-or-buy
  • Robust Load Balancing with Machine Learned Advice
    Peng, Ahmadian, Esfandiari, Mirrokni
    SODA '22
    load balancing
    online
    scheduling
  • Learning-augmented algorithms for online subset sum
    Xu, Zhang
    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
  • Online Graph Algorithms with Predictions
    Azar, Panigrahi, Touitou
    arXiv '21
    SODA '22
    network design
    online
  • Using Machine Learning Predictions to Speed-up Dijkstra's Shortest Path Algorithm
    Feijen, Schäfer
    arXiv '21
    running time
    shortest path
  • Robustification of Online Graph Exploration Methods
    Eberle, Lindermayr, Megow, Nölke, Schlöter
    AAAI '22
    arXiv '21
    exploration
    online
  • Learning-Augmented Algorithms for Online Steiner Tree
    Xu, Moseley
    AAAI '22
    arXiv '21
    network design
    online
  • A Novel Prediction Setup for Online Speed-Scaling
    Antoniadis, Ganje, Shahkarami
    arXiv '21
    SWAT '22
    online
    scheduling
  • Competitive Sequencing with Noisy Advice
    Angelopoulos, Kamali, Shadkami
    arXiv '21
    online
    scheduling
  • Logarithmic Regret from Sublinear Hints
    Bhaskara, Cutkosky, Kumar, Purohit
    arXiv '21
    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
  • Can Q-Learning be Improved with Advice?
    Golowich, Moitra
    arXiv '21
    COLT '22
    learning
  • 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
  • Distortion-Oblivious Algorithms for Minimizing Flow Time
    Azar, Leonardi, Touitou
    arXiv '21
    SODA '22
    online
    scheduling
  • Pareto-optimal learning-augmented algorithms for online conversion problems
    Sun, Lee, Hajiesmaili, Wierman, Tsang
    arXiv '21
    NeurIPS '21
    online
  • Learning to Hash Robustly, Guaranteed
    Andoni, Beaglehole
    arXiv '21
    ICML '22
    locality sensitive hashing
    nearest neighbors search
    running time
  • Faster Matchings via Learned Duals
    Dinitz, Im, Lavastida, Moseley, Vassilvitskii
    arXiv '21
    NeurIPS '21
    matching
    running time
  • Learning Augmented Online Facility Location
    Fotakis, Gergatsouli, Gouleakis, Patris
    arXiv '21
    network design
    online
  • Robust Learning-Augmented Caching: An Experimental Study
    Chłędowski, Polak, Szabucki, Żołna
    arXiv '21
    ICML '21
    caching/paging
    experiments
    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
  • Learning-based support estimation in sublinear time
    Eden, Indyk, Narayanan, Rubinfeld, Silwal, Wagner
    arXiv '21
    ICLR '21
    running time
    sample complexity
    sublinear algorithms
  • Using Predicted Weights for Ad Delivery
    Lavastida, Moseley, Ravi, Xu
    ACDA '21
    arXiv '21
    matching
    online
  • Flow Time Scheduling with Uncertain Processing Time
    Azar, Leonardi, Touitou
    arXiv '21
    STOC '21
    online
    scheduling
  • 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
    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 learned approach to design compressed rank/select data structures
    Boffa, Ferragina, Vinciguerra
    ALENEX '21
    TALG '22
    data structure
  • Learning Online Algorithms with Distributional Advice
    Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, Nikos Zarifis
    ICML '21
    learning
    online
    prophet
    rent-or-buy
  • Putting the \"Learning\" into Learning-Augmented Algorithms for Frequency Estimation
    Du, Wang, Mitzenmacher
    ICML '21
    learning
    streaming
  • 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
    ISAIM '22
    SPAA '21
    online
    scheduling
  • Online Knapsack with Frequency Predictions
    Im, Kumar, Quaem, Purohit
    NeurIPS '21
    online
    packing
  • 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
    online
    scheduling
  • Prediction Augmented Segment Routing
    Kodialam, Lakshman
    HPSR '21
    online
    routing
  • 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
  • Contract scheduling with predictions
    Angelopoulos, Kamali
    AAAI '21
    arXiv '20
    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
    online
    secretary
  • Generalized Sorting with Predictions
    Lu, Ren, Sun, Zhang
    arXiv '20
    SOSA '21
    running time
    sorting
  • 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
  • Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms
    Wei, Zhang
    arXiv '20
    NeurIPS '20
    online
    rent-or-buy
    scheduling
  • Online Search With a Hint
    Angelopoulos
    arXiv '20
    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 Algorithms for Weighted Paging with Predictions
    Jiang, Panigrahi, Su
    arXiv '20
    ICALP '20
    caching/paging
    online
  • Algorithms with Predictions
    Mitzenmacher, Vassilvitskii
    arXiv '20
    BWCA '20
    Commun. ACM '22
    survey
  • Online Page Migration with ML Advice
    Indyk, Mallmann-Trenn, Mitrovic, Rubinfeld
    AISTATS '22
    arXiv '20
    online
    page migration
  • Secretary and Online Matching Problems with Machine Learned Advice
    Antoniadis, Gouleakis, Kleer, Kolev
    arXiv '20
    NeurIPS '20
    matching
    online
    secretary
  • Better and simpler learning-augmented online caching
    Wei
    APPROX-RANDOM '20
    arXiv '20
    caching/paging
    online
  • Online metric algorithms with untrusted predictions
    Antoniadis, Coester, Elias, Polak, Simon
    arXiv '20
    ICML '20
    caching/paging
    k-server
    matching
    MTS
    online
  • Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice
    Wang, Li, Wang
    arXiv '20
    NeurIPS '20
    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
    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 scheduling via learned weights
    Moseley, Vassilvitskii, Lattanzi, Lavastida
    SODA '20
    online
    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
    bidding
    online
    packing
    rent-or-buy
  • Scheduling with Predictions and the Price of Misprediction
    Mitzenmacher
    arXiv '19
    ITCS '20
    online
    queueing
  • A model for learned bloom filters and optimizing by sandwiching
    Mitzenmacher
    arXiv '19
    NeurIPS '18
  • 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
  • Competitive Caching with Machine Learned Advice
    Lykouris, Vassilvitskii
    arXiv '18
    ICML '18
    J. ACM '21
    caching/paging
    online
  • Improving online algorithms via ML predictions
    Purohit, Svitkina, Kumar
    NeurIPS '18
    online
    rent-or-buy
    scheduling
  • The Case for Learned Index Structures
    Kraska, Beutel, Chi, Dean, Polyzotis
    arXiv '17
    SIGMOD Conference '18
    data structure
  • 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
AGT
differential privacy
prior/related work

allocation
auctions
beyond NP hardness
bidding
caching/paging
clustering
convex body chasing
cover problems
covering problems
data-driven
experiments
explorable uncertainty
exploration
k-server
learning
linear quadratic control
load balancing
locality sensitive hashing
matching
matroid intersection
max flow
MTS
multiple predictions
nearest neighbors search
network design
packing
page migration
prophet
queueing
rent-or-buy
routing
sample complexity
scheduling
SDP
search
secretary
set cover
shortest path
sorting
streaming
streaming algorithms
subgraph counting
sublinear algorithms
subset sum
survey