Robust matchings and matroid intersections

DOI10.1137/100808800MaRDI QIDQ5891380zbMATH OpenOpenAlexFDO

Authors Ryo Fujita, Yusuke Kobayashi, Kazuhisa Makino

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

complexitymatchingmatroid intersectionrobustness

Mathematics Subject Classification ID

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

Recommendations

• Robust matchings and matroid intersections
• Robust independence systems
• Robust independence systems
• Robust randomized matchings
• Robust randomized matchings

Cited in

(15)

• Persistency and matroid intersection
• Randomized strategies for cardinality robustness in the knapsack problem
• Surrogate optimization for \(p\)-norms
• Fractionally subadditive maximization under an incremental knapsack constraint
• General bounds for incremental maximization
• scientific article; zbMATH DE number 1617264 (Why is no real title available?)
• Matching as the Intersection of Matroids
• Robust recoverable perfect matchings
• Robust Matchings
• Robust randomized matchings
• Robust randomized matchings
• Robust independence systems
• Robust matchings and matroid intersections
• Randomized strategies for robust combinatorial optimization with approximate separation
• Fractionally Subadditive Maximization under an Incremental Knapsack Constraint with Applications to Incremental Flows

This page was built for publication: Robust matchings and matroid intersections

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