Zobrazeno 1 - 10
of 124
pro vyhledávání: '"Allan Borodin"'
Publikováno v:
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence.
A fundamental question in social choice and multi-agent systems is aggregating ordinal preferences expressed by agents into a measurably prudent collective choice. A promising line of recent work views ordinal preferences as a proxy for underlying ca
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e59170f1da88716f6660245cfcd3cf36
https://doi.org/10.24963/ijcai.2022/17
https://doi.org/10.24963/ijcai.2022/17
Publikováno v:
ACM Journal of Experimental Algorithmics. 25:1-37
We perform an experimental study of algorithms for online bipartite matching under the known i.i.d. input model with integral types. In the last decade, there has been substantial effort in designing complex algorithms with the goal of improving wors
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b8478078a91bcb40da46e58cb198157d
https://doi.org/10.1145/3379552
https://doi.org/10.1145/3379552
Publikováno v:
Borodin, A, Boyar, J, Larsen, K S & Pankratov, D 2020, ' Advice Complexity of Priority Algorithms ', Theory of Computing Systems, vol. 64, no. 4, pp. 593-625 . https://doi.org/10.1007/s00224-019-09955-7
The priority model of "greedy-like" algorithms was introduced by Borodin, Nielsen, and Rackoff in 2002. We augment this model by allowing priority algorithms to have access to advice, i.e., side information precomputed by an all-powerful oracle. Obta
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ae7fa3099c8be2e9f31a2823b28fe78e
https://doi.org/10.1007/s00224-019-09955-7
https://doi.org/10.1007/s00224-019-09955-7
Autor:
Nicolas Pena, Allan Borodin
Publikováno v:
Theoretical Computer Science. 770:1-24
The surprising results of Karp, Vazirani and Vazirani [39] and (respectively) Buchbinder et al. [18] are examples where rather simple randomization provides provably better approximations than the corresponding deterministic counterparts for online b
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d7ad708b9dc1f581fce73f8255427dcd
https://doi.org/10.1016/j.tcs.2018.10.015
https://doi.org/10.1016/j.tcs.2018.10.015
Publikováno v:
Theory of Computing Systems. 63:1781-1818
We present a series of results regarding conceptually simple algorithms for bipartite matching in various online and related models. We first consider a deterministic adversarial model. The best approximation ratio possible for a one-pass determinist
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7bb3a414928639cf5d2bc9fe6ff9b577
https://doi.org/10.1007/s00224-019-09916-0
https://doi.org/10.1007/s00224-019-09916-0
Autor:
Allan Borodin, Brendan Lucier
Publikováno v:
SIAM Journal on Computing. 46:620-660
We consider auctions in which greedy algorithms, paired with first-price or critical-price payment rules, are used to resolve multiparameter combinatorial allocation problems. We study the price of anarchy for social welfare in such auctions. We show
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b8f64f19f190741b435fa0bbe92ec246
https://doi.org/10.1137/15m1048720
https://doi.org/10.1137/15m1048720
Autor:
Allan Borodin, Brendan Lucier
Publikováno v:
ACM Transactions on Economics and Computation. 5:1-23
We study mechanisms for the combinatorial auction (CA) problem, in which m objects are sold to rational agents and the goal is to maximize social welfare. Of particular interest is the special case of s -CAs, where agents are interested in sets of si
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c4add53f6743dc4405344f5a3e3f69dd
https://doi.org/10.1145/2956585
https://doi.org/10.1145/2956585
Publikováno v:
WWW
Motivated by applications to word-of-mouth advertising, we consider a game-theoretic scenario in which competing advertisers want to target initial adopters in a social network. Each advertiser wishes to maximize the resulting cascade of influence, m
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6f1b2069ab9d6ad467c0f0ef0c94c6ed
https://doi.org/10.1007/s00453-016-0169-0
https://doi.org/10.1007/s00453-016-0169-0
Publikováno v:
IJCAI
Gerrymandering is the process by which parties manipulate boundaries of electoral districts in order to maximize the number of districts they can win. Demographic trends show an increasingly strong correlation between residence and party affiliation;
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3cf082013cd601d81d50897e305047a7
https://doi.org/10.24963/ijcai.2018/14
https://doi.org/10.24963/ijcai.2018/14
Publikováno v:
Approximation and Online Algorithms ISBN: 9783030046927
WAOA
WAOA
The priority model of “greedy-like” algorithms was introduced by Borodin, Nielsen, and Rackoff in 2002. We augment this model by allowing priority algorithms to have access to advice, i.e., side information precomputed by an all-powerful oracle.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1c55b0af5328eedd6f75947ddbb15fc0
https://doi.org/10.1007/978-3-030-04693-4_5
https://doi.org/10.1007/978-3-030-04693-4_5
