House Markets with Matroid and Knapsack Constraints

Krysta, PJ and Zhang, J (2016) House Markets with Matroid and Knapsack Constraints. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)., 2016-7-12 - 2016-7-15.

Text House-full.pdf - Author Accepted Manuscript Download (503kB)

Abstract

Classical online bipartite matching problem and its generalizations are central algorithmic optimization problems. The second related line of research is in the area of algorithmic mechanism design, referring to the broad class of house allocation or assignment problems. We introduce a single framework that unifies and generalizes these two streams of models. Our generalizations allow for arbitrary matroid constraints or knapsack constraints at every object in the allocation problem. We design and analyze approximation algorithms and truthful mechanisms for this framework. Our algorithms have best possible approximation guarantees for most of the special instantiations of this framework, and are strong generalizations of the previous known results.

Item Type:	Conference or Workshop Item (Unspecified)
Uncontrolled Keywords:	algorithmic mechanism design, approximation algorithms, matching under preferences, matroid and knapsack constraints
Depositing User:	Symplectic Admin
Date Deposited:	26 Sep 2016 08:42
Last Modified:	19 Jan 2023 07:36
DOI:	10.4230/LIPIcs.ICALP.2016.141
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3001463