Matchings with lower quotas: algorithms and complexity

DOI10.1007/s00453-016-0252-6zbMath1386.68115OpenAlexW2470524007MaRDI QIDQ1702126

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

Publication date: 28 February 2018

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

maximum matchinginapproximabilitybounded treewidthmany-to-one matchingproject allocation

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) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (6)

Simplified group activity selection with group size constraints ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Unnamed Item ⋮ Handling preferences in student-project allocation ⋮ Stable matchings with covering constraints: a complete computational trichotomy ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The hospitals/residents problem with lower quotas
• Improved approximation bounds for the student-project allocation problem with preferences over projects
• Graph factors and factorization: 1985--2003: a survey
• Two algorithms for the student-project allocation problem
• The college admissions problem with lower and common quotas
• Student-project allocation with preferences over projects
• General factors of graphs
• General antifactors of graphs
• Treewidth. Computations and approximations
• Antifactors of graphs
• Some APX-completeness results for cubic graphs
• Tractable cases of the extended global cardinality constraint
• Matching with quorums
• A note on the serial dictatorship with project closures
• Greedy Local Improvement and Weighted Set Packing Approximation
• Profile-Based Optimal Matchings in the Student/Project Allocation Problem
• Weighted Matching in Chess Tournaments
• Cost minimization in wireless networks with a bounded and unbounded number of interfaces
• Algorithmics of Matching Under Preferences
• On the structure of factorizable graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

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