Conference item
Shortest paths without a map, but with an entropic regularizer
- Abstract:
- In a 1989 paper titled 'shortest paths without a map', Papadimitriou and Yannakakis introduced an online model of searching in a weighted layered graph for a target node, while attempting to minimize the total length of the path traversed by the searcher. This problem, later called layered graph traversal, is parametrized by the maximum cardinality k of a layer of the input graph. It is an online setting for dynamic programming, and it is known to be a rather general and fundamental model of online computing, which includes as special cases other acclaimed models. The deterministic competitive ratio for this problem was soon discovered to be exponential in k, and it is now nearly resolved: it lies between O(2k) and O(k2k). Regarding the randomized competitive ratio, in 1993 Ramesh proved, surprisingly, that this ratio has to be at least O(k2/log1+?k) (for any constant ? > 0). In the same paper, Ramesh also gave an O(k13)-competitive randomized online algorithm. Since 1993, no progress has been reported on the randomized competitive ratio of layered graph traversal. In this work we show how to apply the mirror descent framework on a carefully selected evolving metric space, and obtain an O(k2) competitive randomized online algorithm, nearly matching the known lower bound on the randomized competitive ratio.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 266.6KB, Terms of use)
-
- Publisher copy:
- 10.1109/FOCS54457.2022.00036
Authors
- Publisher:
- IEEE
- Host title:
- Proceedings of the IEEE 63RD Annual Symposium on Foundations of Computer Science (FOCS 2022)
- Pages:
- 1102-1113
- Publication date:
- 2022-12-28
- Event title:
- IEEE 63RD Annual Symposium on Foundations of Computer Science (FOCS 2022)
- Event location:
- Denver, CO, USA
- Event website:
- https://focs2022.eecs.berkeley.edu/
- Event start date:
- 2022-10-31
- Event end date:
- 2022-11-03
- DOI:
- EISSN:
-
2575-8454
- ISSN:
-
1523-8288
- ISBN:
- 9781665455190
- Language:
-
English
- Keywords:
- Pubs id:
-
1326742
- Local pid:
-
pubs:1326742
- Deposit date:
-
2023-03-28
Terms of use
- Copyright holder:
- IEEE
- Copyright date:
- 2022
- Rights statement:
- © IEEE 2022
- Notes:
- This paper was presented at the IEEE 63RD Annual Symposium on Foundations of Computer Science (FOCS 2022), 31st October - 3rd November 2023, Denver, CO, USA. This is the accepted manuscript version of the article. The final version is available online from IEEE at: https://doi.org/10.1109/FOCS54457.2022.00036
If you are the owner of this record, you can report an update to it here: Report update to this record