The Complexity of Computing the Random Priority Allocation Matrix

DOI10.1287/moor.2014.0707zbMath1409.91187OpenAlexW2154912294MaRDI QIDQ3465944

Daniela Saban, Jay Sethuraman

Publication date: 29 January 2016

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.2014.0707

zbMATH Keywords

complexitymatchingnetworksgraphsassignmentrandomized algorithmsrandom priority

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68)

Related Items (7)

Favoring Eagerness for Remaining Items: Designing Efficient, Fair, and Strategyproof Mechanisms ⋮ Random Serial Dictatorship: The One and Only ⋮ Complexity of finding Pareto-efficient allocations of highest welfare ⋮ Pareto optimal allocation under uncertain preferences: uncertainty models, algorithms, and complexity ⋮ Counting houses of Pareto optimal matchings in the house allocation problem ⋮ Size versus truthfulness in the house allocation problem ⋮ A pessimist's approach to one-sided matching

Cites Work

• School choice with controlled choice constraints: hard bounds versus soft bounds
• Parametrized algorithms for random serial dictatorship
• The complexity of computing the permanent
• Approximate counting, uniform generation and rapidly mixing Markov chains
• On cores and indivisibility
• Pareto optimality in many-to-many matching problems
• The computational complexity of random serial dictatorship
• College admissions with affirmative action
• Minimum Edge Dominating Sets
• Scheduling with Opting Out: Improving upon Random Priority
• Popular Matchings with Variable Job Capacities
• Strategy-Proof Allocation Mechanisms at Differentiable Points
• Probability Inequalities for Sums of Bounded Random Variables

This page was built for publication: The Complexity of Computing the Random Priority Allocation Matrix