| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427330 | Information Processing Letters | 2014 | 4 Pages |
Abstract
•We study the advice complexity of two online problems.•The problems are online bipartite matching and online stable marriage.•For both problems, we give exact advice complexity.
In this paper, we study the advice complexity of the online bipartite matching problem and the online stable marriage problem. We show that for both problems, ⌈log2(n!)⌉⌈log2(n!)⌉ bits of advice are necessary and sufficient for a deterministic online algorithm to be optimal, where n denotes the number of vertices in one bipartition in the former problem, and the number of men in the latter.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Shuichi Miyazaki,