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.ESA.2019.2
URN: urn:nbn:de:0030-drops-111235
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11123/
Go to the corresponding LIPIcs Volume Portal

Afshani, Peyman ; Fagerberg, Rolf ; Hammer, David ; Jacob, Riko ; Kostitsyna, Irina ; Meyer, Ulrich ; Penschuck, Manuel ; Sitchinava, Nodari

Fragile Complexity of Comparison-Based Algorithms

pdf-format:
LIPIcs-ESA-2019-2.pdf (0.6 MB)

Abstract

We initiate a study of algorithms with a focus on the computational complexity of individual elements, and introduce the fragile complexity of comparison-based algorithms as the maximal number of comparisons any individual element takes part in. We give a number of upper and lower bounds on the fragile complexity for fundamental problems, including Minimum, Selection, Sorting and Heap Construction. The results include both deterministic and randomized upper and lower bounds, and demonstrate a separation between the two settings for a number of problems. The depth of a comparator network is a straight-forward upper bound on the worst case fragile complexity of the corresponding fragile algorithm. We prove that fragile complexity is a different and strictly easier property than the depth of comparator networks, in the sense that for some problems a fragile complexity equal to the best network depth can be achieved with less total work and that with randomization, even a lower fragile complexity is possible.

BibTeX - Entry

@InProceedings{afshani_et_al:LIPIcs:2019:11123,
  author =	{Peyman Afshani and Rolf Fagerberg and David Hammer and Riko Jacob and Irina Kostitsyna and Ulrich Meyer and Manuel Penschuck and Nodari Sitchinava},
  title =	{{Fragile Complexity of Comparison-Based Algorithms}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{2:1--2:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Michael A. Bender and Ola Svensson and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11123},
  URN =		{urn:nbn:de:0030-drops-111235},
  doi =		{10.4230/LIPIcs.ESA.2019.2},
  annote =	{Keywords: Algorithms, comparison based algorithms, lower bounds}
}

Keywords: Algorithms, comparison based algorithms, lower bounds
Collection: 27th Annual European Symposium on Algorithms (ESA 2019)
Issue Date: 2019
Date of publication: 06.09.2019

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