Robust randomized matchings
Author
Abstract
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 α then it is called α-robust. Hassin and Rubinstein [7] gave an algorithm
that returns a 1/
√
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.
Indexation
Artículo de publicación SCOPUS
Identifier
URI: https://repositorio.uchile.cl/handle/2250/169408
DOI: 10.1287/moor.2017.0878
ISSN: 15265471
0364765X
Quote Item
Mathematics of Operations Research, Volumen 43, Issue 2, 2018, Pages 675-692
Collections