License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.141
URN: urn:nbn:de:0030-drops-62853
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6285/
Go to the corresponding LIPIcs Volume Portal

Krysta, Piotr ; Zhang, Jinshan

House Markets with Matroid and Knapsack Constraints

pdf-format:
LIPIcs-ICALP-2016-141.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{krysta_et_al:LIPIcs:2016:6285,
  author =	{Piotr Krysta and Jinshan Zhang},
  title =	{{House Markets with Matroid and Knapsack Constraints}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{141:1--141:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6285},
  URN =		{urn:nbn:de:0030-drops-62853},
  doi =		{10.4230/LIPIcs.ICALP.2016.141},
  annote =	{Keywords: Algorithmic mechanism design; Approximation algorithms; Matching under preferences; Matroid and knapsack constraints}
}

Keywords: Algorithmic mechanism design; Approximation algorithms; Matching under preferences; Matroid and knapsack constraints
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI