Matchings with lower quotas: algorithms and complexity

DOI10.1007/S00453-016-0252-6MaRDI QIDQ1702126zbMATH OpenOpenAlexFDO

Authors Ashwin Arulselvan, Ágnes Cseh, Martin Groß, David F. Manlove, Jannik Matuschke

Publication date 28 February 2018

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-016-0252-6

zbMATH Keywords

bounded treewidthinapproximabilitymany-to-one matchingmaximum matchingproject allocation

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Many-to-one matchings with lower quotas: algorithms and complexity
• Stable matchings with covering constraints: a complete computational trichotomy
• Pareto optimal matchings with lower quotas
• The hospitals/residents problem with lower quotas
• The Hospitals/Residents Problem with Quota Lower Bounds

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A note on the serial dictatorship with project closures
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• Antifactors of graphs
• Cost minimization in wireless networks with a bounded and unbounded number of interfaces
• General antifactors of graphs
• General factors of graphs
• Graph factors and factorization: 1985--2003: a survey
• Greedy local improvement and weighted set packing approximation
• scientific article; zbMATH DE number 5917571 (Why is no real title available?)
• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Improved approximation bounds for the student-project allocation problem with preferences over projects
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Matching with quorums
• On the structure of factorizable graphs
• Profile-based optimal matchings in the student/project allocation problem
• Some APX-completeness results for cubic graphs
• Student-project allocation with preferences over projects
• The college admissions problem with lower and common quotas
• The hospitals/residents problem with lower quotas
• Tractable cases of the extended global cardinality constraint
• Treewidth. Computations and approximations
• Two algorithms for the student-project allocation problem
• Weighted Matching in Chess Tournaments

Cited in

(12)

• Handling preferences in student-project allocation
• Simplified group activity selection with group size constraints
• Model-based approaches to multi-attribute diverse matching
• Stable matchings with covering constraints: a complete computational trichotomy
• A fine-grained view on stable many-to-one matching problems with lower and upper quotas
• A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas
• Many-to-one matchings with lower quotas: algorithms and complexity
• Grundy Distinguishes Treewidth from Pathwidth
• scientific article; zbMATH DE number 7278072 (Why is no real title available?)
• Grundy distinguishes treewidth from pathwidth
• Finding degree-constrained acyclic orientations
• Degrees and gaps: tight complexity results of general factor problems parameterized by treewidth and cutwidth

This page was built for publication: Matchings with lower quotas: algorithms and complexity

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