Simultaneous matchings: Hardness and approximation

DOI10.1016/j.jcss.2008.02.001zbMath1144.68046OpenAlexW2083203323MaRDI QIDQ931730

Irit Katriel, Meena Mahajan, Martin Kuetz, Khaled M. Elbassioni

Publication date: 26 June 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2008.02.001

zbMATH Keywords

bipartite graphNP-completenessmatchingsoptimisationconstraint programmingperfect matchingshardness of approximation

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (4)

Cardinality constraints and systems of restricted representatives ⋮ Structural decompositions for problems with global constraints ⋮ Filtering algorithms for global chance constraints ⋮ Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the system of two all different\(\_\)predicates
• Matching theory
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• On approximation properties of the Independent set problem for degree 3 graphs
• Paths, Trees, and Flowers
• Fundamentals of Computation Theory

This page was built for publication: Simultaneous matchings: Hardness and approximation