Robust Matchings and Matroid Intersections

DOI10.1137/100808800zbMath1285.05136OpenAlexW2079266301MaRDI QIDQ5891380

Ryo Fujita, Kazuhisa Makino, Yusuke Kobayashi

Publication date: 21 January 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/100808800

zbMATH Keywords

complexityrobustnessmatchingmatroid intersection

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (7)

Randomized strategies for cardinality robustness in the knapsack problem ⋮ Randomized strategies for robust combinatorial optimization with approximate separation ⋮ Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows ⋮ Surrogate optimization for \(p\)-norms ⋮ Robust Randomized Matchings ⋮ Fractionally subadditive maximization under an incremental knapsack constraint ⋮ General bounds for incremental maximization

This page was built for publication: Robust Matchings and Matroid Intersections