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

bipartite graphconstraint programminghardness of approximationmatchingsNP-completenessoptimisationperfect matchings

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) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

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

• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation algorithms for NP-hard problems.
• 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?)
• 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

(24)

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

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)