Fragile complexity of comparison-based algorithms

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

doi:10.4230/LIPIcs.ESA.2019.2

Fragile complexity of comparison-based algorithms

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

Institut for Matematik og Datalogi

Aarhus Universitet
IT-Universitetet i København
Eindhoven University of Technology
Goethe University Frankfurt
University of Hawaii System
University of Gothenburg

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

56 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.

Originalsprog	Engelsk
Titel	Proceedings of 27th Annual European Symposium on Algorithms, ESA 2019
Redaktører	Michael A. Bender, Ola Svensson, Grzegorz Herman
Antal sider	19
Forlag	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdato	1. sep. 2019
Sider	2:1-2:19
Artikelnummer	2
ISBN (Elektronisk)	9783959771245
DOI	https://doi.org/10.4230/LIPIcs.ESA.2019.2
Status	Udgivet - 1. sep. 2019
Begivenhed	27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Tyskland Varighed: 9. sep. 2019 → 11. sep. 2019

Konference

Konference	27th Annual European Symposium on Algorithms, ESA 2019
Land/Område	Tyskland
By	Munich/Garching
Periode	09/09/2019 → 11/09/2019

Navn	Leibniz International Proceedings in Informatics
Vol/bind	144
ISSN	1868-8969

Finansiering

∗ 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.

Dokumenter og links

10.4230/LIPIcs.ESA.2019.2Licens: CC BY

Open Access VersionForlagets udgivne version, 649 KBLicens: CC BY

SDU link

Tjek adgangen til materialet i Syddansk Universitetsbiblioteks søgemaskine

1 Ph.d.-afhandling

Some Results on the Theory and Practice of Algorithms
Hammer, D. M. G., aug. 2020, Syddansk Universitet. Det Naturvidenskabelige Fakultet. 136 s.
Publikation: Afhandling › Ph.d.-afhandling

Citationsformater

Afshani, P., Fagerberg, R., Hammer, D., Jacob, R., Kostitsyna, I., Meyer, U., Penschuck, M., & Sitchinava, N. (2019). Fragile complexity of comparison-based algorithms. I M. A. Bender, O. Svensson, & G. Herman (red.), Proceedings of 27th Annual European Symposium on Algorithms, ESA 2019 (s. 2:1-2:19). Artikel 2 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ESA.2019.2

Afshani, Peyman ; Fagerberg, Rolf ; Hammer, David et al. / Fragile complexity of comparison-based algorithms. Proceedings of 27th Annual European Symposium on Algorithms, ESA 2019. red. / Michael A. Bender ; Ola Svensson ; Grzegorz Herman. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. s. 2:1-2:19 (Leibniz International Proceedings in Informatics, Bind 144).

@inproceedings{1cab1b10ec5f4b2880eb0046fb04fb79,

title = "Fragile complexity of comparison-based algorithms",

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.",

keywords = "Algorithms, Comparison based algorithms, Lower bounds",

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

year = "2019",

month = sep,

day = "1",

doi = "10.4230/LIPIcs.ESA.2019.2",

language = "English",

series = "Leibniz International Proceedings in Informatics",

pages = "2:1--2:19",

editor = "Bender, \{Michael A.\} and Ola Svensson and Grzegorz Herman",

booktitle = "Proceedings of 27th Annual European Symposium on Algorithms, ESA 2019",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

address = "Germany",

note = "27th Annual European Symposium on Algorithms, ESA 2019 ; Conference date: 09-09-2019 Through 11-09-2019",

}

Afshani, P, Fagerberg, R, Hammer, D, Jacob, R, Kostitsyna, I, Meyer, U, Penschuck, M & Sitchinava, N 2019, Fragile complexity of comparison-based algorithms. i MA Bender, O Svensson & G Herman (red), Proceedings of 27th Annual European Symposium on Algorithms, ESA 2019., 2, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, bind 144, s. 2:1-2:19, 27th Annual European Symposium on Algorithms, ESA 2019, Munich/Garching, Tyskland, 09/09/2019. https://doi.org/10.4230/LIPIcs.ESA.2019.2

Fragile complexity of comparison-based algorithms. / Afshani, Peyman; Fagerberg, Rolf; Hammer, David et al.
Proceedings of 27th Annual European Symposium on Algorithms, ESA 2019. red. / Michael A. Bender; Ola Svensson; Grzegorz Herman. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. s. 2:1-2:19 2 (Leibniz International Proceedings in Informatics, Bind 144).

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - Fragile complexity of comparison-based algorithms

AU - Afshani, Peyman

AU - Fagerberg, Rolf

AU - Hammer, David

AU - Jacob, Riko

AU - Kostitsyna, Irina

AU - Meyer, Ulrich

AU - Penschuck, Manuel

AU - Sitchinava, Nodari

PY - 2019/9/1

Y1 - 2019/9/1

N2 - 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.

AB - 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.

KW - Algorithms

KW - Comparison based algorithms

KW - Lower bounds

U2 - 10.4230/LIPIcs.ESA.2019.2

DO - 10.4230/LIPIcs.ESA.2019.2

M3 - Article in proceedings

AN - SCOPUS:85074867612

T3 - Leibniz International Proceedings in Informatics

SP - 2:1-2:19

BT - Proceedings of 27th Annual European Symposium on Algorithms, ESA 2019

A2 - Bender, Michael A.

A2 - Svensson, Ola

A2 - Herman, Grzegorz

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 27th Annual European Symposium on Algorithms, ESA 2019

Y2 - 9 September 2019 through 11 September 2019

ER -

Afshani P, Fagerberg R, Hammer D, Jacob R, Kostitsyna I, Meyer U et al. Fragile complexity of comparison-based algorithms. I Bender MA, Svensson O, Herman G, red., Proceedings of 27th Annual European Symposium on Algorithms, ESA 2019. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2019. s. 2:1-2:19. 2. (Leibniz International Proceedings in Informatics, Bind 144). doi: 10.4230/LIPIcs.ESA.2019.2

Fragile complexity of comparison-based algorithms

Abstract

Konference

Finansiering

Dokumenter og links

SDU link

Fingeraftryk

Relaterede publikationer

Some Results on the Theory and Practice of Algorithms

Citationsformater