DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2024.20

Variations on the Tournament Problem

Authors: Fabrizio Luccio, Linda Pagli, and Nicola Santoro

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract

In 1883, Lewis Carrol wrote a newspaper article to criticize how the second best player was determined in a tennis tournament, and to suggest how such a task could be done correctly. This article has been taken by Donald Knuth as the inspiration for efficiently determining the smallest t elements of a totally ordered set of size n using k-comparisons. In the ensuing research, optimal algorithms for some low values of k and t have been established, by Knuth and Aigner; for k = 2 and t ≤ 3, a few new bounds have been established for special values of n. Surprisingly, very little else is known on this problem, in spite of its illustrious pedigree and its relationship to other classical problems (e.g., selection and sorting with k-sorters). Enticed by the undeniable beauty of the problem, and the obvious promise of fun, we have joined the investigative quest. The purpose of this paper is to share some new results obtained so far. We are glad to report advances in two directions.

Cite as

Fabrizio Luccio, Linda Pagli, and Nicola Santoro. Variations on the Tournament Problem. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 20:1-20:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{luccio_et_al:LIPIcs.FUN.2024.20,
  author =	{Luccio, Fabrizio and Pagli, Linda and Santoro, Nicola},
  title =	{{Variations on the Tournament Problem}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{20:1--20:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.20},
  URN =		{urn:nbn:de:0030-drops-199280},
  doi =		{10.4230/LIPIcs.FUN.2024.20},
  annote =	{Keywords: algorithms, parallel algorithms, tournament, selection, ranking}
}

Document

DOI: 10.4230/LIPIcs.FUN.2016.23

An Arithmetic for Rooted Trees

Authors: Fabrizio Luccio

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

Abstract

We propose a new arithmetic for non-empty rooted unordered trees simply called trees. After discussing tree representation and enumeration, we define the operations of tree addition, multiplication, and stretch, prove their properties, and show that all trees can be generated from a starting tree of one vertex. We then show how a given tree can be obtained as the sum or product of two trees, thus defining prime trees with respect to addition and multiplication. In both cases we show how primality can be decided in time polynomial in the number of vertices and prove that factorization is unique. We then define negative trees and suggest dealing with tree equations, giving some preliminary examples. Finally we comment on how our arithmetic might be useful, and discuss preceding studies that have some relations with ours. The parts of this work that do not concur to an immediate illustration of our proposal, including formal proofs, are reported in the Appendix. To the best of our knowledge our proposal is completely new and can be largely modified in cooperation with the readers. To the ones of his age the author suggests that "many roads must be walked down before we call it a theory".

Cite as

Fabrizio Luccio. An Arithmetic for Rooted Trees. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{luccio:LIPIcs.FUN.2016.23,
  author =	{Luccio, Fabrizio},
  title =	{{An Arithmetic for Rooted Trees}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.23},
  URN =		{urn:nbn:de:0030-drops-58687},
  doi =		{10.4230/LIPIcs.FUN.2016.23},
  annote =	{Keywords: Arithmetic, Rooted tree, Prime tree, Tree equation}
}

Search Results

Documents authored by Luccio, Fabrizio

Variations on the Tournament Problem

Abstract

Cite as

An Arithmetic for Rooted Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message