文章基本信息

标题：House Markets with Matroid and Knapsack Constraints
本地全文：下载
作者：Piotr Krysta ; Jinshan Zhang
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：55
页码：141:1-141:14
DOI：10.4230/LIPIcs.ICALP.2016.141
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Algorithmic mechanism design; Approximation algorithms; Matching under preferences; Matroid and knapsack constraints