Robust randomized matchings

DOI10.1287/MOOR.2017.0878MaRDI QIDQ5219560zbMATH OpenOpenAlexFDO

Authors Jannik Matuschke, José A. Soto, Martin Skutella

Publication date 12 March 2020

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.06631

zbMATH Keywords

randomizationrobust matchings

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Matching models (91B68)

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 $alpha$ then it is called $alpha$-robust. In 2002, Hassin and Rubinstein gave an algorithm that returns a $1/sqrt2$-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.

Recommendations

• Robust randomized matchings
• Robust matchings and matroid intersections
• Robust matchings and matroid intersections
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• Competitive weighted matching in transversal matroids

Cites work

• scientific article; zbMATH DE number 5764868 (Why is no real title available?)
• A simple PTAS for weighted matroid matching on strongly base orderable matroids
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computing knapsack solutions with cardinality robustness
• Greedy in Approximation Algorithms
• Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints (extended abstract)
• On the power of randomization in network interdiction
• Packing a knapsack of unknown capacity
• Probability Inequalities for Sums of Bounded Random Variables
• Randomized minmax regret for combinatorial optimization under uncertainty
• Randomized strategies for cardinality robustness in the knapsack problem
• Robust Matchings
• Robust independence systems
• Robust matchings and matroid intersections
• Robust randomized matchings
• Robust subgraphs for trees and paths
• The Concavity and Intersection Properties for Integral Polyhedra
• Worst case analysis of greedy type algorithms for independence systems

Cited in

(14)

• Understanding the correlation gap for matchings
• General bounds for incremental maximization
• On randomized matching mechanisms
• Robust independence systems
• Robust matchings and matroid intersections
• Robust connectivity of graphs on surfaces
• Robust randomized matchings
• scientific article; zbMATH DE number 1617264 (Why is no real title available?)
• Decomposing probability marginals beyond affine requirements
• Robust matchings and matroid intersections
• Optimal multivariate matching before randomization
• Randomized strategies for robust combinatorial optimization with approximate separation
• Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows
• Fractionally subadditive maximization under an incremental knapsack constraint

This page was built for publication: Robust randomized matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5219560)