TY - GEN

T1 - On the Power of Advice and Randomization for Online Bipartite Matching

AU - Dürr, Christoph

AU - Konrad, Christian

AU - Renault, Marc P.

PY - 2016/6/22

Y1 - 2016/6/22

N2 - While randomized online algorithms have access to a sequence of uniform random bits, deterministic online algorithms with advice have access to a sequence of advice bits, i.e., bits that are set by an all-powerful oracle prior to the processing of the request sequence. Advice bits are at least as helpful as random bits, but how helpful are they? In this work, we investigate the power of advice bits and random bits for online maximum bipartite matching (MBM). The well-known Karp-Vazirani-Vazirani algorithm [Karp, Vazirani and Vazirani 90] is an optimal randomized (1-1/e)-competitive algorithm for MBM that requires access to Theta(n log n) uniform random bits. We show that Omega(log(1/epsilon) n) advice bits are necessary and O(1/epsilon^5 n) sufficient in order to obtain a (1-epsilon)-competitive deterministic advice algorithm. Furthermore, for a large natural class of deterministic advice algorithms, we prove that Omega(log log log n) advice bits are required in order to improve on the 1/2-competitiveness of the best deterministic online algorithm, while it is known that O(log n) bits are sufficient [Böckenhauer, Komm, Královic and Královic 2011]. Last, we give a randomized online algorithm that uses cn random bits, for integers c >= 1, and a competitive ratio that approaches 1-1/e very quickly as c is increasing. For example if c = 10, then the difference between 1-1/e and the achieved competitive ratio is less than 0.0002.

AB - While randomized online algorithms have access to a sequence of uniform random bits, deterministic online algorithms with advice have access to a sequence of advice bits, i.e., bits that are set by an all-powerful oracle prior to the processing of the request sequence. Advice bits are at least as helpful as random bits, but how helpful are they? In this work, we investigate the power of advice bits and random bits for online maximum bipartite matching (MBM). The well-known Karp-Vazirani-Vazirani algorithm [Karp, Vazirani and Vazirani 90] is an optimal randomized (1-1/e)-competitive algorithm for MBM that requires access to Theta(n log n) uniform random bits. We show that Omega(log(1/epsilon) n) advice bits are necessary and O(1/epsilon^5 n) sufficient in order to obtain a (1-epsilon)-competitive deterministic advice algorithm. Furthermore, for a large natural class of deterministic advice algorithms, we prove that Omega(log log log n) advice bits are required in order to improve on the 1/2-competitiveness of the best deterministic online algorithm, while it is known that O(log n) bits are sufficient [Böckenhauer, Komm, Královic and Královic 2011]. Last, we give a randomized online algorithm that uses cn random bits, for integers c >= 1, and a competitive ratio that approaches 1-1/e very quickly as c is increasing. For example if c = 10, then the difference between 1-1/e and the achieved competitive ratio is less than 0.0002.

KW - On-line algorithms

KW - Bipartite matching

KW - Randomization

U2 - 10.4230/LIPIcs.ESA.2016.37

DO - 10.4230/LIPIcs.ESA.2016.37

M3 - Conference Contribution (Conference Proceeding)

SN - 9783959770156

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 1

EP - 16

BT - 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark

PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany

ER -