20 July 2020 in ACM Transactions on Algorithms
Consider a two-stage matching problem, where edges of an input graph are revealed in two stages (batches) and in each stage we have to immediately and irrevocably extend our matching using the edges from that stage. The natural greedy algorithm is half competitive. Even though there is a huge literature on online matching in adversarial vertex arrival model , no positive results were previously known in adversarial edge arrival model . For two-stage bipartite matching problem, we show that the optimal competitive ratio is exactly 2/3 in both the fractional and the randomized-integral models. Furthermore, our algorithm for fractional bipartite matching is instance optimal , i.e., it achieves the best competitive ratio for any given first stage graph. We also study natural extensions of this problem to general graphs and to s stages and present randomized-integral algorithms with competitive ratio ½ + 2− O(s) . Our algorithms use a novel Instance-Optimal-LP and combine graph decomposition techniques with online primal-dual analysis.
19 December 2023 in ACM Transactions on Economics and Computation
In a classical online decision problem, a decision-maker who is trying to maximize her value inspects a sequence of arriving items to learn their values (drawn from known distributions) and decides when to stop the process by taking the current item. The goal is to prove a “prophet inequality”: that she can do approximately as well as a prophet with foreknowledge of all the values. In this work, we investigate this problem when the values are allowed to be correlated. Since nontrivial guarantees are impossible for arbitrary correlations, we consider a natural “linear” correlation structure introduced by Bateni et al. as a generalization of the common-base value model of Chawla et al. A key challenge is that threshold-based algorithms, which are commonly used for prophet inequalities, no longer guarantee good performance for linear correlations. We relate this roadblock to another “augmentations” challenge that might be of independent interest: many existing prophet inequality algorithms are not robust to slight increases in the values of the arriving items. We leverage this intuition to prove bounds (matching up to constant factors) that decay gracefully with the amount of correlation of the arriving items. We extend these results to the case of selecting multiple items by designing a new (1+ o (1))-approximation ratio algorithm that is robust to augmentations.
5 February 2021 in Discrete Mathematics