License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.49
URN: urn:nbn:de:0030-drops-154822
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15482/
Shin, Yongho ;
An, Hyung-Chan
Making Three out of Two: Three-Way Online Correlated Selection
Abstract
Two-way online correlated selection (two-way OCS) is an online algorithm that, at each timestep, takes a pair of elements from the ground set and irrevocably chooses one of the two elements, while ensuring negative correlation in the algorithm's choices. Whilst OCS was initially invented by Fahrbach, Huang, Tao, and Zadimoghaddam to break a natural long-standing barrier in the edge-weighted online bipartite matching problem, it is an interesting technique on its own due to its capability of introducing a powerful algorithmic tool, namely negative correlation, to online algorithms. As such, Fahrbach et al. posed two tantalizing open questions in their paper, one of which was the following: Can we obtain n-way OCS for n > 2, in which the algorithm can be given n > 2 elements to choose from at each timestep?
In this paper, we affirmatively answer this open question by presenting a three-way OCS. Our algorithm uses two-way OCS as its building block and is simple to describe; however, as it internally runs two instances of two-way OCS, one of which is fed with the output of the other, the final output probability distribution becomes highly elusive. We tackle this difficulty by approximating the output distribution of OCS by a flat, less correlated function and using it as a safe "surrogate" of the real distribution. Our three-way OCS also yields a 0.5093-competitive algorithm for edge-weighted online matching, demonstrating its usefulness.
BibTeX - Entry
@InProceedings{shin_et_al:LIPIcs.ISAAC.2021.49,
author = {Shin, Yongho and An, Hyung-Chan},
title = {{Making Three out of Two: Three-Way Online Correlated Selection}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {49:1--49:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-214-3},
ISSN = {1868-8969},
year = {2021},
volume = {212},
editor = {Ahn, Hee-Kap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15482},
URN = {urn:nbn:de:0030-drops-154822},
doi = {10.4230/LIPIcs.ISAAC.2021.49},
annote = {Keywords: online correlated selection, multi-way OCS, online algorithms, negative correlation, edge-weighted online bipartite matching}
}
|
Keywords: |
|
online correlated selection, multi-way OCS, online algorithms, negative correlation, edge-weighted online bipartite matching |
|
Collection: |
|
32nd International Symposium on Algorithms and Computation (ISAAC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
30.11.2021 |
