Fragile complexity of comparison-based algorithms

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

DOI

  • Peyman Afshani
  • Rolf Fagerberg, Syddansk Universitet
  • ,
  • David Hammer, Syddansk Universitet, Johann Wolfgang Goethe Universitat Frankfurt am Main
  • ,
  • Riko Jacob, IT-Universitetet i Kobenhavn
  • ,
  • Irina Kostitsyna, Eindhoven University of Technology
  • ,
  • Ulrich Meyer, Johann Wolfgang Goethe Universitat Frankfurt am Main
  • ,
  • Manuel Penschuck, Johann Wolfgang Goethe Universitat Frankfurt am Main
  • ,
  • Nodari Sitchinava

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.

OriginalsprogEngelsk
Titel27th Annual European Symposium on Algorithms, ESA 2019
RedaktørerMichael A. Bender, Ola Svensson, Grzegorz Herman
Antal sider19
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Udgivelsesår2019
Artikelnummer2
ISBN (Elektronisk)9783959771245
DOI
StatusUdgivet - 2019
Begivenhed27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Tyskland
Varighed: 9 sep. 201911 sep. 2019

Konference

Konference27th Annual European Symposium on Algorithms, ESA 2019
LandTyskland
ByMunich/Garching
Periode09/09/201911/09/2019
SerietitelLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind144
ISSN1868-8969

Se relationer på Aarhus Universitet Citationsformater

ID: 172713870