Secretary and Online Matching Problems with Machine Learned Advice
Authors: Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, Pavel Kolev
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | Antonios Antoniadis Universität zu Köln Köln, Germany antoniadis@cs.uni-koeln.de Themis Gouleakis Max Planck Institute for Informatics Saarland Informatics Campus Saarbrücken, Germany tgouleak@mpi-inf.mpg.de Pieter Kleer Max Planck Institute for Informatics Saarland Informatics Campus Saarbrücken, Germany pkleer@mpi-inf.mpg.de Pavel Kolev Max Planck Institute for Informatics Saarland Informatics Campus Saarbrücken, Germany pkolev@mpi-inf.mpg.de |
| Pseudocode | Yes | ALGORITHM 1: Value-maximization secretary algorithm |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository for the methodology described. |
| Open Datasets | No | The paper focuses on theoretical analysis of online algorithms and does not describe experiments performed on a specific dataset for training, validation, or testing. Therefore, no information about publicly available datasets is provided. |
| Dataset Splits | No | The paper does not describe empirical experiments involving data splits for training, validation, or testing, as it focuses on theoretical algorithm design and analysis. |
| Hardware Specification | No | The paper presents theoretical analysis and algorithm design and does not describe any empirical experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper focuses on theoretical algorithm design and competitive analysis and does not describe any specific software implementations or dependencies with version numbers. |
| Experiment Setup | No | The paper provides theoretical parameters for its algorithms (e.g., λ and c in Algorithm 1) which are used for analytical purposes, but it does not describe an empirical experimental setup with details such as hyperparameters, training configurations, or system-level settings. |