Making Three out of Two: Three-Way Online Correlated Selection

Yongho Shin, Hyung Chan An

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

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.

Original languageEnglish
Title of host publication32nd International Symposium on Algorithms and Computation, ISAAC 2021
EditorsHee-Kap Ahn, Kunihiko Sadakane
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772143
DOIs
Publication statusPublished - 2021 Dec 1
Event32nd International Symposium on Algorithms and Computation, ISAAC 2021 - Fukuoka, Japan
Duration: 2021 Dec 62021 Dec 8

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume212
ISSN (Print)1868-8969

Conference

Conference32nd International Symposium on Algorithms and Computation, ISAAC 2021
Country/TerritoryJapan
CityFukuoka
Period21/12/621/12/8

Bibliographical note

Publisher Copyright:
© Yongho Shin and Hyung-Chan An.

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Making Three out of Two: Three-Way Online Correlated Selection'. Together they form a unique fingerprint.

Cite this