@inproceedings{8cde812dda074470ba0a061d58d0c65f,
title = "Online State Exploration: Competitive Worst Case and Learning-Augmented Algorithms",
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.",
keywords = "Competitive Ratio, Learning-augmented Algorithms, Online Algorithms, Online Search, Worst-case Analysis",
author = "Sungjin Im and Benjamin Moseley and Chenyang Xu and Ruilong Zhang",
note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2023 ; Conference date: 18-09-2023 Through 22-09-2023",
year = "2023",
doi = "10.1007/978-3-031-43421-1\_20",
language = "英语",
isbn = "9783031434204",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "333--348",
editor = "Danai Koutra and Claudia Plant and \{Gomez Rodriguez\}, Manuel and Elena Baralis and Francesco Bonchi",
booktitle = "Machine Learning and Knowledge Discovery in Databases",
address = "德国",
}