Empirical Competitive Analysis for the Online Assignment Problem with ML Predictions

DOI

10.2991/978-94-6463-388-7_4How to use a DOI?

Keywords

online assignment problem; machine-learned advice; competitive

Abstract

The online assignment problem, also known as the onlineweighted bipartite matching, produces the smallest weight perfect matching given a complete bipartite graph. The problem is a variant where one part of the graph is known in advance, while the other part is revealed one vertex at a time. Moreover, all the incident edges are revealed as a new vertex arrives. This computational problem plays an important role in the fields of operational research and computer science. 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. It has been proven that for this problem, no online deterministic algorithm can achieve a competitive ratio better than (2n − 1) and no online randomized algorithm can achieve an expected competitive ratio better than ln n. 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 paper, 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 (ML) algorithm that predicts the whole input in advance. We utilize an optimal offline algorithm to provide a matching from the predicted input. Furthermore, we investigate how the prediction error of ML affects the competitive ratio of the online algorithm. We utilize a benchmark data set to perform our empirical analysis of the solution quality. We show that as the ML 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. We show that our proposed online algorithm for the online assignment problem with ML prediction significantly outperforms the optimal deterministic online algorithm for the assignment problem. Also, we show that for some tolerable errors, i.e., for ML prediction with RMSD(A,A′) > 10, our proposed online algorithm has a better solution quality. Otherwise, we propose the use of the existing best randomized online algorithm for the assignment problem. The trade-off for the solution quality is the running time of the online algorithm which is highly dependent on the optimal offline algorithm and the ML predictor.

Copyright

© 2024 The Author(s)

Open Access

Open Access This chapter is licensed under the terms of the Creative Commons Attribution-NonCommercial 4.0 International License (http://creativecommons.org/licenses/by-nc/4.0/), which permits any noncommercial use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

Download article (PDF)

TY  - CONF
AU  - Clarence Gabriel R. Kasilag
AU  - Pollux M. Rey
AU  - Jhoirene B. Clemente
PY  - 2024
DA  - 2024/02/29
TI  - Empirical Competitive Analysis for the Online Assignment Problem with ML Predictions
BT  - Proceedings of the Workshop on Computation: Theory and Practice (WCTP 2023)
PB  - Atlantis Press
SP  - 38
EP  - 54
SN  - 2589-4900
UR  - https://doi.org/10.2991/978-94-6463-388-7_4
DO  - 10.2991/978-94-6463-388-7_4
ID  - Kasilag2024
ER  -