Robust Randomized Matchings

DOI10.1287/moor.2017.0878zbMath1436.91087arXiv1705.06631OpenAlexW2776000100MaRDI QIDQ5219560

Jannik Matuschke, Martin Skutella, Jose A. Soto

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 involving graphs (91A43) Matching models (91B68) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (5)

Robust Connectivity of Graphs on Surfaces ⋮ 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 ⋮ General bounds for incremental maximization

Cites Work

• Unnamed Item
• Randomized strategies for cardinality robustness in the knapsack problem
• On the power of randomization in network interdiction
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computing knapsack solutions with cardinality robustness
• A simple PTAS for weighted matroid matching on strongly base orderable matroids
• Robust subgraphs for trees and paths
• Packing a Knapsack of Unknown Capacity
• Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints
• Randomized Minmax Regret for Combinatorial Optimization Under Uncertainty
• Worst case analysis of greedy type algorithms for independence systems
• The Concavity and Intersection Properties for Integral Polyhedra
• Robust Matchings
• Probability Inequalities for Sums of Bounded Random Variables
• Robust randomized matchings
• Greedy in Approximation Algorithms
• Robust Matchings and Matroid Intersections
• Robust Independence Systems

This page was built for publication: Robust Randomized Matchings