TY - GEN
T1 - House markets with matroid and knapsack constraints
AU - Krysta, Piotr
AU - Jinshan, Zhang
N1 - Publisher Copyright:
© Piotr Krysta and Jinshan Zhng.
PY - 2016/8/1
Y1 - 2016/8/1
N2 - 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.
AB - 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.
KW - Algorithmic mechanism design
KW - Approximation algorithms
KW - Matching under preferences
KW - Matroid and knapsack constraints
UR - https://www.scopus.com/pages/publications/85012877490
UR - https://www.scopus.com/pages/publications/85012877490#tab=citedBy
U2 - 10.4230/LIPIcs.ICALP.2016.141
DO - 10.4230/LIPIcs.ICALP.2016.141
M3 - Conference contribution
AN - SCOPUS:85012877490
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
A2 - Rabani, Yuval
A2 - Chatzigiannakis, Ioannis
A2 - Sangiorgi, Davide
A2 - Mitzenmacher, Michael
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
Y2 - 12 July 2016 through 15 July 2016
ER -