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 language | English |
---|---|
Title of host publication | Proc. 27th Annual European Symposium on Algorithms (ESA) |
Editors | Michael A. Bender, Ola Svensson, Grzegorz Herman |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Number of pages | 19 |
ISBN (Electronic) | 9783959771245 |
DOIs | |
Publication status | Published - Sept 2019 |
Event | 27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Germany Duration: 9 Sept 2019 → 11 Sept 2019 |
Publication series
Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 144 |
ISSN (Print) | 1868-8969 |
Conference
Conference | 27th Annual European Symposium on Algorithms, ESA 2019 |
---|---|
Country/Territory | Germany |
City | Munich/Garching |
Period | 9/09/19 → 11/09/19 |
Funding
∗ This material is based upon work partially performed while attending AlgoPARC Workshop on Parallel Algorithms and Data Structures at the University of Hawaii at Manoa, in part supported by the National Science Foundation under Grant No. CCF-1745331. Funding Rolf Fagerberg: Supported by the Independent Research Fund Denmark, Natural Sciences, grant DFF-7014-00041. David Hammer: Supported by the Deutsche Forschungsgemeinschaft (DFG) under grants ME 2088/3-2 and ME 2088/4-2. Ulrich Meyer: Supported by the Deutsche Forschungsgemeinschaft (DFG) under grants ME 2088/3-2 and ME 2088/4-2. Manuel Penschuck: Supported by the Deutsche Forschungsgemeinschaft (DFG) under grants ME 2088/3-2 and ME 2088/4-2. Nodari Sitchinava: Supported by the National Science Foundation under Grant No. CCF-1533823.
Keywords
- Algorithms
- Comparison based algorithms
- Lower bounds
- comparison based algorithms
- lower bounds