DROPS

Document

DOI: 10.4230/LIPIcs.ICALP.2016.141

House Markets with Matroid and Knapsack Constraints

Authors: Piotr Krysta and Jinshan Zhang

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

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.

Cite as

Piotr Krysta and Jinshan Zhang. House Markets with Matroid and Knapsack Constraints. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 141:1-141:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{krysta_et_al:LIPIcs.ICALP.2016.141,
  author =	{Krysta, Piotr and Zhang, Jinshan},
  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 =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.141},
  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}
}

Search Results

Documents authored by Zhang, Jinshan

House Markets with Matroid and Knapsack Constraints

Abstract

Cite as

Thanks for your feedback!

Could not send message