Counting houses of Pareto optimal matchings in the house allocation problem

DOI10.1016/j.disc.2016.05.027zbMath1401.91453arXiv1401.5354MaRDI QIDQ738845

Andrei Asinowski, Balázs Keszegh, Tillmann Miltzow

Publication date: 16 August 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1401.5354

zbMATH Keywords

combinatorics; complexity; algorithm; counting problem; allocation problem; Pareto optimal matching

Mathematics Subject Classification ID

90C29: Multi-objective and goal programming

91B68: Matching models

Related Items

Partial-matching RMS distance under translation: combinatorics and algorithms, Set systems related to a house allocation problem

Cites Work

• Parametrized algorithms for random serial dictatorship
• Queue allocation of indivisible goods
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• Complexity of generalized satisfiability counting problems
• Pareto optimality in many-to-many matching problems
• The computational complexity of random serial dictatorship
• Minimum Partial-Matching and Hausdorff RMS-Distance under Translation: Combinatorics and Algorithms
• The Complexity of Computing the Random Priority Allocation Matrix
• Algorithmics of Matching Under Preferences
• Computational Complexity
• Algorithmic Game Theory
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Algorithms and Computation
• College Admissions and the Stability of Marriage