License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.42
URN: urn:nbn:de:0030-drops-133867
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13386/
Go to the corresponding LIPIcs Volume Portal

Chen, Ke ; Dumitrescu, Adrian

Multiparty Selection

pdf-format:
LIPIcs-ISAAC-2020-42.pdf (0.5 MB)

Abstract

Given a sequence A of n numbers and an integer (target) parameter 1 ≤ i ≤ n, the (exact) selection problem is that of finding the i-th smallest element in A. An element is said to be (i,j)-mediocre if it is neither among the top i nor among the bottom j elements of S. The approximate selection problem is that of finding an (i,j)-mediocre element for some given i,j; as such, this variant allows the algorithm to return any element in a prescribed range. In the first part, we revisit the selection problem in the two-party model introduced by Andrew Yao (1979) and then extend our study of exact selection to the multiparty model. In the second part, we deduce some communication complexity benefits that arise in approximate selection. In particular, we present a deterministic protocol for finding an approximate median among k players.

BibTeX - Entry

@InProceedings{chen_et_al:LIPIcs:2020:13386,
  author =	{Ke Chen and Adrian Dumitrescu},
  title =	{{Multiparty Selection}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{42:1--42:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13386},
  URN =		{urn:nbn:de:0030-drops-133867},
  doi =		{10.4230/LIPIcs.ISAAC.2020.42},
  annote =	{Keywords: approximate selection, mediocre element, comparison algorithm, i-th order statistic, tournaments, quantiles, communication complexity}
}

Keywords: approximate selection, mediocre element, comparison algorithm, i-th order statistic, tournaments, quantiles, communication complexity
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI