Newest first
133 papers
- Predictive Flows for Faster Ford-FulkersonDavies, Moseley, Vassilvitskii, WangarXiv '23max flowrunning time
- Online Interval Scheduling with PredictionsBoyar, Favrholdt, Kamali, LarsenarXiv '23allocationonlinescheduling
- Online Minimum Spanning Trees with Weight PredictionsBerg, Boyar, Favrholdt, LarsenarXiv '23network designonline
- Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive AnalysisShin, Lee, Lee, AnarXiv '23onlinerent-or-buy
- Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not NecessaryLindermayr, Megow, RapparXiv '23onlinescheduling
- Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster L-/L-Convex Function MinimizationSakaue, OkiarXiv '23running time
- Minimalistic Predictions to Schedule Jobs with Online Precedence ConstraintsLassota, Lindermayr, Megow, SchlöterarXiv '23onlinescheduling
- Renyi-Ulam Games and Online Computation with Imperfect AdviceAngelopoulos, KamaliarXiv '23auctionsonlinepackingsearch
- Graph Searching with PredictionsBanerjee, Cohen-Addad, Gupta, LiarXiv '22ITCS '23explorationonlinesearch
- Scheduling with PredictionsCho, Henderson, ShmoysarXiv '22onlinescheduling
- Mechanism Design With Predictions for Obnoxious Facility LocationIstrate, BonchisarXiv '22AGTmechanism design
- Improved Learning-augmented Algorithms for k-means and k-medians ClusteringThy Nguyen, Anamay Chaturvedi, Huy NguyenarXiv '22ICLR '23clustering
- On the Power of Learning-Augmented BSTsChen, ChenarXiv '22data structuresearch
- Algorithms with Prediction PortfoliosDinitz, Im, Lavastida, Moseley, VassilvitskiiarXiv '22load balancingmatchingmultiple predictionsonlinescheduling
- Private Algorithms with Private PredictionsAmin, Dick, Khodak, VassilvitskiiarXiv '22differential privacy
- Paging with Succinct PredictionsAntoniadis, Boyar, Eliáš, Favrholdt, Hoeksma, Larsen, Polak, SimonarXiv '22caching/pagingonline
- Proportionally Fair Online Allocation of Public Goods with PredictionsBanerjee, Gkatzelis, Hossain, Jin, Micha, ShaharXiv '22allocationonline
- Canadian Traveller Problem with PredictionsBampis, Escoffier, XefterisarXiv '22WAOA '22onlinerouting
- Learning-Augmented Algorithms for Online Linear and Semidefinite ProgrammingGrigorescu, Lin, Silwal, Song, ZhouarXiv '22covering problemsonlineSDP
- Strategyproof Scheduling with PredictionsBalkanski, Gkatzelis, TanarXiv '22ITCS '23AGTscheduling
- Learning-Augmented Maximum FlowPolak, ZubarXiv '22max flowrunning time
- Online Prediction in Sub-linear SpacePeng, ZhangarXiv '22SODA '23learningonline
- Learning-Augmented Query Policies for Minimum Spanning Tree with UncertaintyErlebach, Lima, Megow, SchlöterarXiv '22ESA '22explorable uncertaintynetwork designonline
- Online TSP with PredictionsHu, Wei, Li, Chung, LiaoarXiv '22onlinerouting
- Learning-Augmented Binary Search TreesLin, Luo, WoodruffarXiv '22ICML '22data structuresearch
- Chasing Convex Bodies and Functions with Black-Box AdviceChristianson, Handina, WiermanarXiv '22COLT '22convex body chasingonline
- Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage ModelJin, MaarXiv '22matchingonline
- Learning-Augmented Algorithms for Online TSP on the LineGouleakis, Lakis, ShahkaramiarXiv '22onlinerouting
- A Universal Error Measure for Input Predictions Applied to Online Graph ProblemsBernardini, Lindermayr, Marchetti-Spaccamela, Megow, Stougie, SweeringarXiv '22network designonlinerouting
- Mechanism Design with PredictionsXu, LuarXiv '22IJCAI '22AGTauctionsscheduling
- Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with PredictionsSakaue, OkiarXiv '22matchingmatroid intersectionrunning time
- A Regression Approach to Learning-Augmented Online AlgorithmsAnand, Ge, Kumar, PanigrahiarXiv '22NeurIPS '21learningonline
- Customizing ML Predictions For Online AlgorithmsAnand, Ge, PanigrahiarXiv '22ICML '20learningonlinerent-or-buy
- Improved Price of Anarchy via PredictionsGkatzelis, Kollias, Sgouritsa, TanarXiv '22EC '22AGT
- Online Algorithms with Multiple PredictionsAnand, Ge, Kumar, PanigrahiarXiv '22ICML '22cover problemsmultiple predictionsonline
- Scheduling with Speed PredictionsBalkanski, Ou, Stein, WeiarXiv '22onlinescheduling
- Faster Fundamental Graph Algorithms via Learned PredictionsChen, Silwal, Vakilian, ZhangarXiv '22ICML '22matchingrunning timeshortest path
- Learning-Augmented k-means ClusteringErgun, Feng, Silwal, Woodruff, ZhouarXiv '22ICLR '22beyond NP hardnessclusteringrunning time
- Learning-Augmented Mechanism Design: Leveraging Predictions for Facility LocationAgrawal, Balkanski, Gkatzelis, Ou, TanarXiv '22EC '22AGTnetwork design
- Triangle and Four Cycle Counting with Predictions in Graph StreamsChen, Eden, Indyk, Lin, Narayanan, Rubinfeld, Silwal, Wagner, Woodruff, ZhangarXiv '22ICLR '22streamingsubgraph countingsublinear algorithms
- Online Unit Profit Knapsack with Untrusted PredictionsBoyar, Favrholdt, LarsenarXiv '22SWAT '22onlinepacking
- Permutation Predictions for Non-Clairvoyant SchedulingLindermayr, MegowarXiv '22SPAA '22onlinescheduling
- Single-Leg Revenue Management with AdviceBalseiro, Kroer, KumararXiv '22
- Learning Predictions for Algorithms with PredictionsKhodak, Balcan, Talwalkar, VassilvitskiiarXiv '22learningonline
- Parsimonious Learning-Augmented CachingIm, Kumar, Petety, PurohitarXiv '22ICML '22caching/pagingonline
- Lazy Lagrangians with Predictions for Online LearningAnderson, Iosifidis, LeitharXiv '22learningonline
- Distortion-Oblivious Algorithms for Scheduling on Multiple MachinesAzar, Peretz, TouitouISAAC '22onlinescheduling
- Scheduling with Untrusted PredictionsBampis, Dogeas, Kononov, Lucarelli, PascualIJCAI '22onlinescheduling
- Machine Learning Advised Ski Rental Problem with a DiscountBhattacharya, DasWALCOM '22onlinerent-or-buy
- Robust Load Balancing with Machine Learned AdvicePeng, Ahmadian, Esfandiari, MirrokniSODA '22load balancingonlinescheduling
- Learning-augmented algorithms for online subset sumXu, ZhangJ. Global Optimization '22onlinesubset sum
- Brief Announcement: Towards a More Robust Algorithm for Flow Time Scheduling with PredictionsZhao, Li, Li, ZomayaSPAA '22onlinescheduling
- Uniform Machine Scheduling with PredictionsZhao, Li, ZomayaICAPS '22onlinescheduling
- Real-Time Scheduling with PredictionsZhao, Li, ZomayaRTSS '22onlinescheduling
- Online Graph Algorithms with PredictionsAzar, Panigrahi, TouitouarXiv '21SODA '22network designonline
- Using Machine Learning Predictions to Speed-up Dijkstra's Shortest Path AlgorithmFeijen, SchäferarXiv '21running timeshortest path
- Robustification of Online Graph Exploration MethodsEberle, Lindermayr, Megow, Nölke, SchlöterAAAI '22arXiv '21explorationonlinesearch
- Learning-Augmented Algorithms for Online Steiner TreeXu, MoseleyAAAI '22arXiv '21network designonline
- A Novel Prediction Setup for Online Speed-ScalingAntoniadis, Ganje, ShahkaramiarXiv '21SWAT '22onlinescheduling
- Competitive Sequencing with Noisy AdviceAngelopoulos, Kamali, ShadkamiarXiv '21onlinescheduling
- Logarithmic Regret from Sublinear HintsBhaskara, Cutkosky, Kumar, PurohitarXiv '21NeurIPS '21learningonline
- Learning-Augmented Dynamic Power Management with Multiple States via New Ski-Rental BoundsAntoniadis, Coester, Elias, Polak, SimonarXiv '21NeurIPS '21onlinerent-or-buy
- Can Q-Learning be Improved with Advice?Golowich, MoitraarXiv '21COLT '22learning
- Online Facility Location with PredictionsJiang, Liu, Lyu, Tang, ZhangarXiv '21ICLR '22network designonline
- Online Primal-Dual Algorithms with Predictions for Packing ProblemsDürr, ThangarXiv '21onlinepacking
- Uniform Bounds for Scheduling with Job Size EstimatesScully, Grosof, MitzenmacherarXiv '21ITCS '22onlinequeueing
- Distortion-Oblivious Algorithms for Minimizing Flow TimeAzar, Leonardi, TouitouarXiv '21SODA '22onlinescheduling
- Pareto-optimal learning-augmented algorithms for online conversion problemsSun, Lee, Hajiesmaili, Wierman, TsangarXiv '21NeurIPS '21online
- Learning to Hash Robustly, GuaranteedAndoni, BeagleholearXiv '21ICML '22locality sensitive hashingnearest neighbors searchrunning time
- Faster Matchings via Learned DualsDinitz, Im, Lavastida, Moseley, VassilvitskiiarXiv '21NeurIPS '21matchingrunning time
- Learning Augmented Online Facility LocationFotakis, Gergatsouli, Gouleakis, PatrisarXiv '21network designonline
- Robust Learning-Augmented Caching: An Experimental StudyChłędowski, Polak, Szabucki, ŻołnaarXiv '21ICML '21caching/pagingexperimentsonline
- Robustness and Consistency in Linear Quadratic Control with Untrusted PredictionsLi, Yang, Qu, Shi, Yu, Wierman, LowarXiv '21Proc. ACM Meas. Anal. Comput. Syst. '22SIGMETRICS '22linear quadratic controlonline
- Learning-based support estimation in sublinear timeEden, Indyk, Narayanan, Rubinfeld, Silwal, WagnerarXiv '21ICLR '21running timesample complexitysublinear algorithms
- Using Predicted Weights for Ad DeliveryLavastida, Moseley, Ravi, XuACDA '21arXiv '21matchingonline
- Flow Time Scheduling with Uncertain Processing TimeAzar, Leonardi, TouitouarXiv '21STOC '21onlinescheduling
- Double Coverage with Machine-Learned AdviceLindermayr, Megow, SimonarXiv '21ITCS '22k-serveronline
- Online Bin Packing with PredictionsAngelopoulos, Kamali, ShadkamiarXiv '21IJCAI '22onlinepacking
- Online Bipartite Matching with Predicted DegreesAamand, Chen, IndykarXiv '21matchingonline
- Online Facility Location with Multiple AdviceAlmanza, Chierichetti, Lattanzi, Panconesi, ReNeurIPS '21network designonline
- A learned approach to design compressed rank/select data structuresBoffa, Ferragina, VinciguerraALENEX '21TALG '22data structure
- Learning Online Algorithms with Distributional AdviceIlias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, Nikos ZarifisICML '21learningonlineprophetrent-or-buy
- Putting the \"Learning\" into Learning-Augmented Algorithms for Frequency EstimationDu, Wang, MitzenmacherICML '21learningstreaming
- On the performance of learned data structuresFerragina, Lillo, VinciguerraTheor. Comput. Sci. '21data structure
- Repetition- and Linearity-Aware Rank/Select DictionariesFerragina, Manzini, VinciguerraISAAC '21data structure
- Non-Clairvoyant Scheduling with PredictionsIm, Kumar, Quaem, PurohitISAIM '22SPAA '21onlinescheduling
- Online Knapsack with Frequency PredictionsIm, Kumar, Quaem, PurohitNeurIPS '21onlinepacking
- Online peak-aware energy scheduling with untrusted adviceLee, Maghakian, Hajiesmaili, Sitaraman, Liue-Energy '21SIGENERGY '22onlinescheduling
- Online Unrelated Machine Load Balancing with Predictions RevisitedLi, XianICML '21onlinescheduling
- A New Approach to Capacity Scaling Augmented With Unreliable Machine Learning PredictionsRutten, MukherjeearXiv '21onlinescheduling
- Prediction Augmented Segment RoutingKodialam, LakshmanHPSR '21onlinerouting
- Data-driven Competitive Algorithms for Online Knapsack and Set CoverZeynali, Sun, Hajiesmaili, WiermanAAAI '21arXiv '20data-drivenlearningonlinepackingset cover
- Contract scheduling with predictionsAngelopoulos, KamaliAAAI '21arXiv '20onlinescheduling
- Learnable and Instance-Robust Predictions for Online Matching, Flows and Load BalancingLavastida, Moseley, Ravi, XuarXiv '20ESA '21allocationmatchingonlinescheduling
- Learning-Augmented Weighted PagingBansal, Coester, Kumar, Purohit, VeearXiv '20SODA '22caching/pagingonline
- Online Paging with a Vanishing RegretEmek, Kutten, ShiarXiv '20ITCS '21caching/pagingonline
- Secretaries with AdviceDüttung, Lattanzi, Leme, VassilvitskiiarXiv '20EC '21onlinesecretary
- Generalized Sorting with PredictionsLu, Ren, Sun, ZhangarXiv '20SOSA '21running timesorting
- Learning Augmented Energy Minimization via Speed ScalingBamas, Maggiori, Rohwedder, SvenssonarXiv '20NeurIPS '20onlinescheduling
- The Primal-Dual method for Learning Augmented AlgorithmsBamas, Maggiori, SvenssonarXiv '20NeurIPS '20onlinerent-or-buyset cover
- Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online AlgorithmsWei, ZhangarXiv '20NeurIPS '20onlinerent-or-buyscheduling
- Online Search With a HintAngelopoulosarXiv '20ITCS '21onlinesearch
- Online Nash Social Welfare Maximization with PredictionsBanerjee, Gkatzelis, Gorokh, JinarXiv '20SODA '22online
- Queues with Small AdviceMitzenmacherACDA '21arXiv '20onlinequeueing
- Online Algorithms for Weighted Paging with PredictionsJiang, Panigrahi, SuACM Trans. Algorithms '22arXiv '20ICALP '20caching/pagingonline
- Algorithms with PredictionsMitzenmacher, VassilvitskiiarXiv '20BWCA '20Commun. ACM '22survey
- Online Page Migration with ML AdviceIndyk, Mallmann-Trenn, Mitrovic, RubinfeldAISTATS '22arXiv '20onlinepage migration
- Secretary and Online Matching Problems with Machine Learned AdviceAntoniadis, Gouleakis, Kleer, KolevarXiv '20NeurIPS '20matchingonlinesecretary
- Better and simpler learning-augmented online cachingWeiAPPROX-RANDOM '20arXiv '20caching/pagingonline
- Online metric algorithms with untrusted predictionsAntoniadis, Coester, Elias, Polak, SimonarXiv '20ICML '20caching/pagingk-servermatchingMTSonline
- Online Algorithms for Multi-shop Ski Rental with Machine Learned AdviceWang, Li, WangarXiv '20NeurIPS '20onlinerent-or-buy
- Improving Online Rent-or-Buy Algorithms with Sequential Decision Making and ML PredictionsBanerjeeNeurIPS '20onlinerent-or-buy
- Untrusted Predictions Improve Trustable Query PoliciesErlebach, Hoffmann, de Lima, Megow, SchlöterarXiv '20online
- The PGM-index: a fully-dynamic compressed learned index with provable worst-case boundsFerragina, VinciguerraProc. VLDB Endow. '20data structure
- Learning-augmented data stream algorithmsJiang, Li, Lin, Ruan, WoodruffICLR '20streaming
- Online scheduling via learned weightsMoseley, Vassilvitskii, Lattanzi, LavastidaSODA '20onlinescheduling
- Near-optimal bounds for online caching with machine learned adviceRohatgiarXiv '19SODA '20caching/pagingonline
- (Learned) Frequency Estimation Algorithms under Zipfian DistributionAamand, Indyk, VakilianarXiv '19streaming
- The Supermarket Model with Known and Predicted Service TimesMitzenmacher, Dell AmicoarXiv '19IEEE Trans. Parallel Distributed Syst. '22
- Online Computation with Untrusted AdviceAngelopoulos, Dürr, Jin, Kamali, RenaultarXiv '19ITCS '20biddingonlinepackingrent-or-buy
- Scheduling with Predictions and the Price of MispredictionMitzenmacherarXiv '19ITCS '20onlinequeueing
- A model for learned bloom filters and optimizing by sandwichingMitzenmacherarXiv '19NeurIPS '18
- Learned data structuresFerragina, VinciguerraINNSBDDL '19data structure
- Online algorithms for rent-or-buy with expert adviceGollapudi, PanigrahiICML '19onlinerent-or-buy
- Learning-Based Frequency Estimation AlgorithmsHsu, Indyk, Katabi, VakilianICLR '19streaming
- Learning-Based Low-Rank ApproximationsIndyk, Vakilian, YuanarXiv '19NeurIPS '19
- Competitive Caching with Machine Learned AdviceLykouris, VassilvitskiiarXiv '18ICML '18J. ACM '21caching/pagingonline
- Improving online algorithms via ML predictionsPurohit, Svitkina, KumarNeurIPS '18onlinerent-or-buyscheduling
- The Case for Learned Index StructuresKraska, Beutel, Chi, Dean, PolyzotisarXiv '17SIGMOD Conference '18data structure
- Revenue optimization with approximate bid predictionsMedina, VassilvitskiiarXiv '17NIPS '17prior/related work
- Optimal online assignment with forecastsVee, Vassilvitskii, ShanmugasundaramEC '10prior/related work
- The adwords problem: online keyword matching with budgeted bidders under random permutationsDevanur, HayesEC '09prior/related work
- Allocating online advertisement space with unreliable estimatesMahdian, Nazerzadeh, SaberiEC '07prior/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
mechanism design
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
subgraph counting
sublinear algorithms
subset sum
survey