Simultaneous matchings: Hardness and approximation

DOI10.1016/J.JCSS.2008.02.001MaRDI QIDQ931730zbMATH OpenOpenAlexFDO

Authors Irit Katriel, Meena Mahajan, Martin Kuetz, Khaled 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

optimisationbipartite graphconstraint programmingNP-completenessperfect matchingshardness of approximationmatchings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Algorithms and Computation
• Bottleneck subset-type restricted matching problems
• Perfect matching in bipartite hypergraphs subject to a demand graph
• Partitioning to three matchings of given size is NP-complete for bipartite graphs
• The \(b\)-matching problem in hypergraphs: hardness and approximability

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1151367 (Why is no real title available?)
• scientific article; zbMATH DE number 2080315 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• Approximation algorithms for NP-hard problems.
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Inapproximability results for bounded variants of optimization problems.
• Matching theory
• On approximation properties of the Independent set problem for degree 3 graphs
• On the system of two all different\(\_\)predicates
• Paths, Trees, and Flowers

Cited in

(23)

• Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems
• Computational complexity of simultaneous elementary matching problems
• The minimum maximal k-partial-matching problem
• Cardinality constraints and systems of restricted representatives
• On the maximum edge-pair embedding bipartite matching
• On the maximum edge-pair embedding bipartite matching
• Structural decompositions for problems with global constraints
• A note on the hardness results for the labeled perfect matching problems in bipartite graphs
• Solving (large scale) matching problems combinatorially
• Complexity of matching problems
• Hardness and approximation of minimum maximal matchings
• Matchings under distance constraints. I
• \(\mathcal{IV}\)-matching is strongly \textsf{NP}-hard
• Bottleneck subset-type restricted matching problems
• Matchings under distance constraints. II.
• Multitasking capacity: hardness results and improved constructions
• Filtering algorithms for global chance constraints
• Matching with sizes (or scheduling with processing set restrictions)
• Matching with sizes (or scheduling with processing set restrictions)
• The Complexity of Rationalizing Matchings
• On tree-constrained matchings and generalizations
• On tree-constrained matchings and generalizations
• Algorithms and Computation

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

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