Multidimensional Stable Roommates with Master List

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F20%3A00345575" target="_blank" >RIV/68407700:21240/20:00345575 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-030-64946-3_5" target="_blank" >https://doi.org/10.1007/978-3-030-64946-3_5</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-64946-3_5" target="_blank" >10.1007/978-3-030-64946-3_5</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Multidimensional Stable Roommates with Master List

Popis výsledku v původním jazyce

Since the early days of research in algorithms and complexity, the computation of stable matchings is a core topic. While in the classic setting the goal is to match up two agents (either from different “gender” (this is Stable Marriage) or “unrestricted” (this is Stable Roommates)), Knuth [1976] triggered the study of three- or multidimensional cases. Here, we focus on the study of Multidimensional Stable Roommates, known to be ???????? -hard since the early 1990’s. Many ???????? -hardness results, however, rely on very general input instances that do not occur in at least some of the specific application scenarios. With the quest for identifying islands of tractability, we look at the case of master lists. Here, as natural in applications where agents express their preferences based on “objective” scores, one roughly speaking assumes that all agent preferences are “derived from” a central master list, implying that the individual agent preferences shall be similar. Master lists have been frequently studied in the two-dimensional (classic) stable matching case, but seemingly almost never for the multidimensional case. This work, also relying on methods from parameterized algorithm design and complexity analysis, performs a first systematic study of Multidimensional Stable Roommates under the assumption of master lists.

Název v anglickém jazyce

Multidimensional Stable Roommates with Master List

Popis výsledku anglicky

Since the early days of research in algorithms and complexity, the computation of stable matchings is a core topic. While in the classic setting the goal is to match up two agents (either from different “gender” (this is Stable Marriage) or “unrestricted” (this is Stable Roommates)), Knuth [1976] triggered the study of three- or multidimensional cases. Here, we focus on the study of Multidimensional Stable Roommates, known to be ???????? -hard since the early 1990’s. Many ???????? -hardness results, however, rely on very general input instances that do not occur in at least some of the specific application scenarios. With the quest for identifying islands of tractability, we look at the case of master lists. Here, as natural in applications where agents express their preferences based on “objective” scores, one roughly speaking assumes that all agent preferences are “derived from” a central master list, implying that the individual agent preferences shall be similar. Master lists have been frequently studied in the two-dimensional (classic) stable matching case, but seemingly almost never for the multidimensional case. This work, also relying on methods from parameterized algorithm design and complexity analysis, performs a first systematic study of Multidimensional Stable Roommates under the assumption of master lists.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Web and Internet Economics - 16th International Conference, WINE 2020, Beijing, China, December 7-11, 2020, Proceedings

ISBN

978-3-030-64945-6

ISSN

—

e-ISSN

—

Počet stran výsledku

15

Strana od-do

59-73

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Beijing

Datum konání akce

7. 12. 2020

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—