Solving the Online Assignment Problem with Machine Learned Advice
- URL: http://arxiv.org/abs/2208.04016v1
- Date: Mon, 8 Aug 2022 09:54:22 GMT
- Title: Solving the Online Assignment Problem with Machine Learned Advice
- Authors: Clarence Gabriel R. Kasilag, Pollux M. Rey, Jhoirene B. Clemente
- Abstract summary: We provide an online algorithm for the online assignment problem by simulating a machine learning algorithm that predicts the whole input in advance.
We show that as the Machine Learning prediction error increases, the solution quality decreases.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The online assignment problem plays an important role in operational research
and computer science which is why immense attention has been given to improving
its solution quality. Due to the incomplete information about the input, it is
difficult for online algorithms to produce the optimal solution. The quality of
the solution of an online algorithm is measured using a competitive ratio. No
online deterministic algorithm can achieve a competitive ratio better than
(2n-1). It has been shown that advice in online computation improves the lower
bound of the competitive ratio of online problems. Advice in online computation
can be interpreted as additional information for the online algorithm to
compensate for the lack of information about the whole input sequence. In this
study, we investigate how introducing machine-learned advice could improve the
competitive ratio for this problem. We provide an online algorithm for the
online assignment problem by simulating a machine learning algorithm that
predicts the whole input in advance. We utilize an optimal offline algorithm to
provide a matching solution from the predicted input. Furthermore, we
investigate how the prediction error of machine learning affects the
competitive ratio of the online algorithm. We utilize a benchmark data set to
perform our empirical analysis. We show that as the Machine Learning prediction
error increases, the solution quality decreases. Moreover, the magnitude of
error is directly proportional to the size of the input. This result is
analogous to the competitive ratio of the best deterministic algorithm for the
online assignment problem which is dependent also on the parameter n.
Related papers
- Understanding the performance gap between online and offline alignment algorithms [63.137832242488926]
We show that offline algorithms train policy to become good at pairwise classification, while online algorithms are good at generations.
This hints at a unique interplay between discriminative and generative capabilities, which is greatly impacted by the sampling process.
Our study sheds light on the pivotal role of on-policy sampling in AI alignment, and hints at certain fundamental challenges of offline alignment algorithms.
arXiv Detail & Related papers (2024-05-14T09:12:30Z) - Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
Recent advances in algorithmic design show how to utilize predictions obtained by machine learning models from past and present data.
Prior research in this context was focused on a paradigm where the predictor is pre-trained on past data and then used as a black box.
In this work, we unpack the predictor and integrate the learning problem it gives rise for within the algorithmic challenge.
arXiv Detail & Related papers (2024-03-12T08:40:21Z) - Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms [11.029788598491077]
We study online conversion with switching costs, a family of online problems that capture emerging problems at the intersection of energy and sustainability.
We introduce competitive (robust) threshold-based algorithms for both the deterministic and deterministic variants of this problem.
We then propose learning-augmented algorithms that take advantage of black-box advice to achieve significantly better average-case performance.
arXiv Detail & Related papers (2023-10-31T16:34:49Z) - Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental
Problem via Best-Possible Competitive Analysis [0.1529342790344802]
We present improved learning-augmented algorithms for the multi-option ski rental problem.
Our algorithm is based on a new, provably best-possible randomized competitive algorithm for the problem.
arXiv Detail & Related papers (2023-02-14T05:05:03Z) - Robustification of Online Graph Exploration Methods [59.50307752165016]
We study a learning-augmented variant of the classical, notoriously hard online graph exploration problem.
We propose an algorithm that naturally integrates predictions into the well-known Nearest Neighbor (NN) algorithm.
arXiv Detail & Related papers (2021-12-10T10:02:31Z) - Adversarial Deep Learning for Online Resource Allocation [12.118811903399951]
We use deep neural networks to learn an online algorithm for a resource allocation and pricing problem from scratch.
Our work is the first using deep neural networks to design an online algorithm from the perspective of worst-case performance guarantee.
arXiv Detail & Related papers (2021-11-19T15:48:43Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms.
For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime.
In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem.
We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
arXiv Detail & Related papers (2021-09-13T18:10:52Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
We study the fundamental online $k$-server problem in a learning-augmented setting.
We show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff.
arXiv Detail & Related papers (2021-03-02T11:04:33Z) - Metrical Task Systems with Online Machine Learned Advice [0.0]
We show that augmenting online algorithms with a machine learned predictor can provably decrease the competitive ratio under as long as the predictor is suitably accurate.
We focus on the specific class of uniform task systems on $n$ tasks, for which the best deterministic algorithm is $O(n)$ competitive and the best randomized algorithm is $O(log n)$ competitive.
arXiv Detail & Related papers (2020-12-17T04:56:51Z) - Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online
Algorithms [85.97516436641533]
We study the problem of improving the performance of online algorithms by incorporating machine-learned predictions.
The goal is to design algorithms that are both consistent and robust.
We provide the first set of non-trivial lower bounds for competitive analysis using machine-learned predictions.
arXiv Detail & Related papers (2020-10-22T04:51:01Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.