Robust Randomized Matchings

• 成果类型: Article
• 署名作者: Matuschke, Jannik; Skutella, Martin; Soto, Jose A.
• 署名单位: Technical University of Munich; Technical University of Munich; Technical University of Berlin; Universidad de Chile; Universidad de Chile
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2017.0878
• 发表日期: 2018
• 页码: 675-692
• 关键词: independence systems; algorithms; greedy

摘要

The following game is played on a weighted graph: Alice selects a matching M and Bob selects a number k. Alice's payoff is the ratio of the weight of the k heaviest edges of M to the maximum weight of a matching of size at most k. If M guarantees a payoff of at least a then it is called alpha-robust. In 2002, Hassin and Rubinstein gave an algorithm that returns a 1/root 2 -robust matching, which is best possible. We show that Alice can improve her payoff to 1/ln(4) by playing a randomized strategy. This result extends to a very general class of independence systems that includes matroid intersection, b-matchings, and strong 2-exchange systems. It also implies an improved approximation factor for a stochastic optimization variant known as the maximum priority matching problem and translates to an asymptotic robustness guarantee for deterministic matchings, in which Bob can only select numbers larger than a given constant. Moreover, we give a new LP-based proof of Hassin and Rubinstein's bound.