Document Open Access Logo

Fragile Complexity of Comparison-Based Algorithms

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

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.2.pdf
  • Filesize: 0.63 MB
  • 19 pages

Document Identifiers

Author Details

Peyman Afshani
  • Aarhus University, Denmark
Rolf Fagerberg
  • University of Southern Denmark, Odense, Denmark
David Hammer
  • Goethe University Frankfurt, Germany
  • University of Southern Denmark, Odense, Denmark
Riko Jacob
  • IT University of Copenhagen, Denmark
Irina Kostitsyna
  • TU Eindhoven, The Netherlands
Ulrich Meyer
  • Goethe University Frankfurt, Germany
Manuel Penschuck
  • Goethe University Frankfurt, Germany
Nodari Sitchinava
  • University of Hawaii at Manoa

Funding

  • Fagerberg, Rolf: Supported by the Independent Research Fund Denmark, Natural Sciences, grant DFF-7014-00041.
  • Hammer, David: Supported by the Deutsche Forschungsgemeinschaft (DFG) under grants ME 2088/3-2 and ME 2088/4-2.
  • Meyer, Ulrich: Supported by the Deutsche Forschungsgemeinschaft (DFG) under grants ME 2088/3-2 and ME 2088/4-2.
  • Penschuck, Manuel: Supported by the Deutsche Forschungsgemeinschaft (DFG) under grants ME 2088/3-2 and ME 2088/4-2.
  • Sitchinava, Nodari: Supported by the National Science Foundation under Grant No. CCF-1533823.

Acknowledgements

We thank Steven Skiena for posing the original problem, and we thank Michael Bender, Rob Johnson, and Pat Morin for helpful discussions.

Cite AsGet BibTex

Peyman Afshani, Rolf Fagerberg, David Hammer, Riko Jacob, Irina Kostitsyna, Ulrich Meyer, Manuel Penschuck, and Nodari Sitchinava. Fragile Complexity of Comparison-Based Algorithms. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 2:1-2:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.2

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Algorithms
  • comparison based algorithms
  • lower bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. P. Afshani, R. Fagerberg, D. Hammer, R. Jacob, I. Kostitsyna, U. Meyer, M. Penschuck, and N. Sitchinava. Fragile Complexity of Comparison-Based Algorithms. CoRR, abs/1901.02857, 2019. URL: http://arxiv.org/abs/1901.02857.
  2. M. Ajtai, J. Komlós, and E. Szemerédi. An O(n log n) Sorting Network. In Proceedings of the 15th Symposium on Theory of Computation, STOC '83, pages 1-9. ACM, 1983. URL: https://doi.org/10.1145/800061.808726.
  3. M. Ajtai, J. Komlós, and E. Szemerédi. Sorting in c log n parallel steps. Combinatorica, 3(1):1-19, March 1983. URL: https://doi.org/10.1007/BF02579338.
  4. M. Ajtai, J. Komlós, and E. Szemerédi. Halvers and Expanders. In IEEE, editor, FOCS'92, pages 686-692, Pittsburgh, PN, October 1992. IEEE Computer Society Press. Google Scholar
  5. V. E. Alekseev. Sorting Algorithms with minimum memory. Kibernetika, 5(5):99-103, 1969. Google Scholar
  6. K. E. Batcher. Sorting Networks and their Applications. Proceedings of AFIPS Spring Joint Computer Conference, pages 307-314, 1968. Google Scholar
  7. G. Stølting Brodal and M. C. Pinotti. Comparator Networks for Binary Heap Construction. In Proc. 6th Scandinavian Workshop on Algorithm Theory, volume 1432 of LNCS, pages 158-168. Springer Verlag, Berlin, 1998. URL: https://doi.org/10.1007/BFb0054364.
  8. V. Chvátal. Lecture notes on the new AKS sorting network. Technical Report DCS-TR-294, Department of Computer Science, Rutgers University, New Brunswick, NJ, 1992, October. Google Scholar
  9. R. Cole. Parallel Merge Sort. SIAM Journal on Computing, 17(4):770-785, 1988. Google Scholar
  10. M. Dowd, Y. Perl, L. Rudolph, and M. Saks. The periodic balanced sorting network. J. ACM, 36(4):738-757, 1989, October. Google Scholar
  11. R. W. Floyd. Algorithm 245: Treesort. Commun. ACM, 7(12):701, December 1964. URL: https://doi.org/10.1145/355588.365103.
  12. M. T. Goodrich. Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time. In David B. Shmoys, editor, STOC'14, pages 684-693. ACM, 2014. URL: http://dl.acm.org/citation.cfm?id=2591796.
  13. S. Janson. Tail bounds for sums of geometric and exponential variables. Statistics & Probability Letters, 135:1-6, 2018. URL: https://doi.org/10.1016/j.spl.2017.11.017.
  14. S. Jimbo and A. Maruoka. A Method of Constructing Selection Networks with O(log n) Depth. SIAM Journal on Computing, 25(4):709-739, 1996. Google Scholar
  15. I. Parberry. The pairwise sorting network. Parallel Processing Letters, 2(2-3):205-211, 1992. Google Scholar
  16. B. Parker and I. Parberry. Constructing sorting networks from k-sorters. Information Processing Letters, 33(3):157-162, 30 nov 1989. Google Scholar
  17. M. S. Paterson. Improved sorting networks with O(log N) depth. Algorithmica, 5(1):75-92, 1990. Google Scholar
  18. N. Pippenger. Selection Networks. SIAM Journal on Computing, 20(5):878-887, 1991. Google Scholar
  19. V. R. Pratt. Shellsort and Sorting Networks. Outstanding Dissertations in the Computer Sciences. Garland Publishing, New York, 1972. Google Scholar
  20. J. I. Seiferas. Sorting Networks of Logarithmic Depth, Further Simplified. Algorithmica, 53(3):374-384, 2009. Google Scholar
  21. S.Hoory, N. Linial, and A. Wigderson. Expander Graphs and Their Applications. BAMS: Bulletin of the American Mathematical Society, 43:439-561, 2006. Google Scholar
  22. S. P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1-3):1-336, 2012. Google Scholar
  23. A. Yao and F. F. Yao. Lower Bounds on Merging Networks. J. ACM, 23(3):566-571, 1976. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact