Symmetric interdiction for matching problems

DOI10.4230/LIPICS.APPROX-RANDOM.2017.9MaRDI QIDQ5002612zbMATH OpenFDO

Authors Samuel Haney, Bruce M. Maggs, Biswaroop Maiti, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram

Publication date 28 July 2021

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2017.9

zbMATH Keywords

approximation algorithmsinterdiction digital objectmatching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Matching interdiction
• Interdiction problems on planar graphs
• Interdicting structured combinatorial optimization problems with {0,1}-objectives
• Hardness and approximation for network flow interdiction
• Interdiction problems on planar graphs

Cites work

• A problem in network interdiction
• Deterministic network interdiction
• Geometric algorithms and combinatorial optimization.
• scientific article; zbMATH DE number 6515828 (Why is no real title available?)
• scientific article; zbMATH DE number 7005721 (Why is no real title available?)
• Matching interdiction
• Network flow interdiction on planar graphs
• Notes about the Carathéodory number
• Odd Minimum Cut-Sets and b-Matchings
• On a generalization of Schönhardt's polyhedron
• On Budgeted Optimization Problems
• On complexity of special maximum matchings constructing
• On short paths interdiction problems: Total and node-wise limited interdiction
• On the history of the transportation and maximum flow problems
• Optimal interdiction policy for a flow network
• The Demand-Matching Problem
• The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability

Cited in

(5)

• On asymmetric matching between sets
• Perfect matching interdiction problem restricted to a stable vertex
• Symmetry-preserving matchings
• Matching interdiction
• Disconnectedness brings robustness? On network design for matching with vertex interdiction

This page was built for publication: Symmetric interdiction for matching problems

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