ScholarMate
WeChat
Sina
Facebook
Share link
Summary
Eden, Feige, and Feldman explored the concept of the max-min greedy matching problem, which can be conceived as a game played between an algorithm and an adversary. Both parties are presented with a bipartite graph consisting of items and players. Initially, the algorithm selects a priority order for the items, while the adversary, in turn, chooses a priority order for the players based on the algorithm's choice. These priority orders are then utilized in a greedy process to establish a matching between the items and players. During the process, when it is a player's turn, they select the highest priority item from their remaining available neighbors. The objective of the algorithm is to maximize the size of the resulting matching, while the adversary's goal is to minimize its size. Previous studies have demonstrated that the algorithm can employ a polynomial-time strategy to achieve a competitive ratio greater than 21.In this research, we present evidence that, from the adversary's standpoint, approximating the adversarial order minimum matching problem with a ratio better than 56 is NP-hard, assuming the small set expansion (SSE) hypothesis. Conversely, we introduce a fractional variant of the problem and analyze the interaction between the algorithm and the adversary when either or both parties are allowed to utilize fractional permutations. Notably, we discover that if the algorithm solely employs integral item permutations, then an optimal response from the adversary can also involve integral player permutations. Additionally, we establish that, in the fractional variant, the algorithm can adopt a round-robin strategy to achieve a competitive ratio of at least 1 - 1/e. Furthermore, we demonstrate that the analysis for the round-robin strategy is tight even for regular graphs.
