On the complexity of fair house allocation
type: Item
instance of: scholarly article
title: On the complexity of fair house allocation
author: Naoyuki Kamiyama
author: Pasin Manurangsi
author: Warut Suksompong
published in: Operations Research Letters
publication date: 2021-12-13T00:00:00Z
full work available at URL: https://arxiv.org/abs/2106.06925
Mathematics Subject Classification ID: 91-XX
Mathematics Subject Classification ID: 68-XX
zbMATH DE Number: 7443062
zbMATH Keywords: house allocation
zbMATH Keywords: assignment
zbMATH Keywords: fairness
zbMATH Keywords: envy-freeness
zbMATH Keywords: proportionality
zbMATH Keywords: equitability
MaRDI profile type: Publication
OpenAlex ID: W3169332944
cites work: Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
cites work: Algorithms and Computation
cites work: Bicovering: Covering edges with two small subsets of vertices
cites work: Fair Allocation of Indivisible Goods
cites work: Relations between average case complexity and approximation complexity
cites work: Envy-freeness in house allocation problems
cites work: Q4198056
cites work: The Impossibility of Bayesian Group Decision Making with Separate Aggregation of Beliefs and Values
cites work: On the power of unique 2-prover 1-round games
cites work: Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
cites work: Hardness of Bipartite Expansion.
cites work: Size versus truthfulness in the house allocation problem
cites work: Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
cites work: Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis
cites work: Graph expansion and the unique games conjecture
cites work: A Stab at Approximating Minimum Subadditive Join
cites work: On a conjecture by Gale about one-sided matching problems
DOI: 10.1016/J.ORL.2021.06.006
description: scientific article; zbMATH DE number 7443062