Zobrazeno 1 - 10
of 12
pro vyhledávání: '"Klaus Heeger"'
Publikováno v:
Journal of Artificial Intelligence Research. 71:993-1048
We initiate the study of external manipulations in Stable Marriage by considering several manipulative actions as well as several manipulation goals. For instance, one goal is to make sure that a given pair of agents is matched in a stable solution,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::49b355fb8cd6deb6e96e129d2f9a94d0
https://doi.org/10.1613/jair.1.12755
https://doi.org/10.1613/jair.1.12755
Publikováno v:
Algorithmic Game Theory ISBN: 9783031157134
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::df8b6c8711e8d69668a3356ad3e99139
https://doi.org/10.1007/978-3-031-15714-1_25
https://doi.org/10.1007/978-3-031-15714-1_25
Publikováno v:
Information and Computation. 289:104943
We continue and extend previous work on the parameterized complexity analysis of the NP-hard Stable Roommates with Ties and Incomplete Lists problem, thereby strengthening earlier results both on the side of parameterized hardness as well as on the s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d2e9bd0ac59064fe01313c0dd73a36e7
https://doi.org/10.1016/j.ic.2022.104943
https://doi.org/10.1016/j.ic.2022.104943
Following up on purely theoretical work of Bredereck et al. [AAAI 2020], we contribute further theoretical insights into adapting stable two-sided matchings to change. Moreover, we perform extensive empirical studies hinting at numerous practically u
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8ee22ff44f177ebe8a5aa414e78405c3
Autor:
Klaus Heeger, Danny Hermelin, George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Dvir Shabtay
Publikováno v:
35th AAAI Conference on Artificial Intelligence (AAAI), Vancouver, Canada, 2-9 February 2021 [Conference proceedings]
We introduce a natural but seemingly yet unstudied generalization of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. Our generalization lies in simultaneously considering several instances of the problem
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::740f23877fdaceeae06ed591861aa89f
http://arxiv.org/abs/2010.04643
http://arxiv.org/abs/2010.04643
Autor:
Niclas Boehmer, Klaus Heeger
In the Hospital Residents problem with lower and upper quotas ($HR-Q^U_L$), the goal is to find a stable matching of residents to hospitals where the number of residents matched to a hospital is either between its lower and upper quota or zero [Bir\'
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6ecbdabe07db2e3981ee7259308a3bb3
http://arxiv.org/abs/2009.14171
http://arxiv.org/abs/2009.14171
Autor:
Klaus Heeger, Niclas Boehmer
Publikováno v:
Web and Internet Economics ISBN: 9783030649456
WINE
WINE
In the Hospital Residents problem with lower and upper quotas (HR- \({Q}_{L}^{U}\)), the goal is to find a stable matching of residents to hospitals where the number of residents matched to a hospital is either between its lower and upper quota or ze
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b23a2e005410d963af71a9110fcfa0ea
https://doi.org/10.1007/978-3-030-64946-3_3
https://doi.org/10.1007/978-3-030-64946-3_3
Publikováno v:
Algorithmic Game Theory ISBN: 9783030579791
SAGT
SAGT
We initiate the study of external manipulations in Stable Marriage by considering several manipulative actions as well as several “desirable” manipulation goals. For instance, one goal is to make sure that a given pair of agents is matched in a s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::27049827abd404966bbb1b836f75866c
https://doi.org/10.1007/978-3-030-57980-7_11
https://doi.org/10.1007/978-3-030-57980-7_11
Publikováno v:
Web and Internet Economics ISBN: 9783030649456
WINE
WINE
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 “un
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5c4d9bd6c9e1bd98aa32d099e178a166
https://doi.org/10.1007/978-3-030-64946-3_5
https://doi.org/10.1007/978-3-030-64946-3_5
Autor:
Klaus Heeger, Jens Vygen
Publikováno v:
SIAM Journal on Discrete Mathematics. 31:1820-1835
We present a $\frac{10}{7}$-approximation algorithm for the minimum 2-vertex-connected spanning subgraph problem. Similarly to the work of Cheriyan, Sebo, and Szigeti for 2-edge-connected spanning subgraphs, our algorithm is based on computing a care
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ef92f2ac9c71537f3d8ce402513e7fa5
https://doi.org/10.1137/16m1091587
https://doi.org/10.1137/16m1091587