Online State Exploration: Competitive Worst Case and Learning-Augmented Algorithms
Lists
Only you see this
Abstract
This paper introduces the online state exploration problem. In the problem, there is a hidden d-dimensional target state. We are given a distance function between different states in the space and a penalty function depending on the current state for each incorrect guess. The goal is to move to a vector that dominates the target state starting from the origin in the d-dimensional space while minimizing the total distance and penalty cost. This problem generalizes several natural online discrete optimization problems such as multi-dimensional knapsack cover, cow path, online bidding, and online search. For online state exploration, the paper gives results in the worst-case competitive analysis model and in the online algorithms augmented with the prediction model. The results extend and generalize many known results in the online setting.
BibTeX
@inproceedings{im2023online,
author = {Sungjin Im and Benjamin Moseley and Chenyang Xu and Ruilong Zhang},
title = {{Online State Exploration: Competitive Worst Case and Learning-Augmented Algorithms}},
booktitle = {ECML/PKDD},
year = {2023},
doi = {10.1007/978-3-031-43421-1\_20},
}Loading related content...