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 treewidthinapproximabilitymaximum matchingmany-to-one matchingproject allocation

Mathematics Subject Classification ID

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) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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

• 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?)
• 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
• 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

(10)

• Handling preferences in student-project allocation
• Simplified group activity selection with group size constraints
• Many-to-one matchings with lower quotas: algorithms and complexity
• scientific article; zbMATH DE number 7278072 (Why is no real title available?)
• 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
• Stable matchings with covering constraints: a complete computational trichotomy
• Grundy distinguishes treewidth from pathwidth
• Model-based approaches to multi-attribute diverse matching
• Grundy Distinguishes Treewidth from Pathwidth

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)