Fragile complexity of comparison-based algorithms

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

14 Downloads (Pure)

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.

Original languageEnglish
Title of host publicationProc. 27th Annual European Symposium on Algorithms (ESA)
EditorsMichael A. Bender, Ola Svensson, Grzegorz Herman
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages19
ISBN (Electronic)9783959771245
DOIs
Publication statusPublished - Sep 2019
Event27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Germany
Duration: 9 Sep 201911 Sep 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume144
ISSN (Print)1868-8969

Conference

Conference27th Annual European Symposium on Algorithms, ESA 2019
CountryGermany
CityMunich/Garching
Period9/09/1911/09/19

Keywords

  • Algorithms
  • Comparison based algorithms
  • Lower bounds
  • comparison based algorithms
  • lower bounds

Fingerprint Dive into the research topics of 'Fragile complexity of comparison-based algorithms'. Together they form a unique fingerprint.

Cite this