Secretary and online matching problems with machine learned advice
From MaRDI portal
Abstract: The classical analysis of online algorithms, due to its worst-case nature, can be quite pessimistic when the input instance at hand is far from worst-case. Often this is not an issue with machine learning approaches, which shine in exploiting patterns in past inputs in order to predict the future. However, such predictions, although usually accurate, can be arbitrarily poor. Inspired by a recent line of work, we augment three well-known online settings with machine learned predictions about the future, and develop algorithms that take them into account. In particular, we study the following online selection problems: (i) the classical secretary problem, (ii) online bipartite matching and (iii) the graphic matroid secretary problem. Our algorithms still come with a worst-case performance guarantee in the case that predictions are subpar while obtaining an improved competitive ratio (over the best-known classical online algorithm for each problem) when the predictions are sufficiently accurate. For each algorithm, we establish a trade-off between the competitive ratios obtained in the two respective cases.
Cites work
- A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
- Algorithms for Secretary Problems on Graphs and Hypergraphs
- An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions
- Competitive k-server algorithms
- Competitive Analysis with a Sample and the Secretary Problem
- Competitive Caching with Machine Learned Advice
- Competitive weighted matching in transversal matroids
- Dynamic Programming and Decision Theory
- scientific article; zbMATH DE number 3383344 (Why is no real title available?)
- Matroid prophet inequalities and applications to multi-dimensional mechanism design
- Matroid Secretary Problems
- Near-Optimal Bounds for Online Caching with Machine Learned Advice
- Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
- Online Optimization with Uncertain Information
- Online Scheduling via Learned Weights
- Online vertex-weighted bipartite matching and single-bid budgeted allocations
- Online vertex-weighted bipartite matching. Beating \(1-\frac{1}{e}\) with random arrivals
- Prophet inequalities for independent and identically distributed random variables from an unknown distribution
- Prophet Inequalities with Limited Information
- Prophet secretary for combinatorial auctions and matroids
- Robust Algorithms for the Secretary Problem
- Scheduling with Predictions and the Price of Misprediction
- Secretary Problems with Non-Uniform Arrival Order
- Secretary problems: weights and discounts
- Strong algorithms for the ordinal matroid secretary problem
- The Two-Sided Game of Googol and Sample-Based Prophet Inequalities
Cited in
(8)- Learning-augmented algorithms for online subset sum
- Online interval scheduling with predictions
- Online unit profit knapsack with predictions
- Online budget-feasible mechanism design with predictions
- Online delay management on a single train line with predictions
- Online unbounded knapsack
- Online interval scheduling with predictions
- A new impossibility result for online bipartite matching problems
This page was built for publication: Secretary and online matching problems with machine learned advice
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6108930)
