Search Results

Documents authored by Pagli, Linda

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
Complete Volume
DOI: 10.4230/LIPIcs.FUN.2018
LIPIcs, Volume 100, FUN'18, Complete Volume

Authors: Hiro Ito, Stefano Leonardi, Linda Pagli, and Giuseppe Prencipe

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
LIPIcs, Volume 100, FUN'18, Complete Volume
Cite as

9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{ito_et_al:LIPIcs.FUN.2018,
  title =	{{LIPIcs, Volume 100, FUN'18, Complete Volume}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018},
  URN =		{urn:nbn:de:0030-drops-89311},
  doi =		{10.4230/LIPIcs.FUN.2018},
  annote =	{Keywords: Theory of computation, Complexity classes, Algorithm design techniques, Computability, Approximation algorithms analysis, Mathematics of computing}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.FUN.2018.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Hiro Ito, Stefano Leonardi, Linda Pagli, and Giuseppe Prencipe

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 0:i-0:xi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ito_et_al:LIPIcs.FUN.2018.0,
  author =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{0:i--0:xi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.0},
  URN =		{urn:nbn:de:0030-drops-87914},
  doi =		{10.4230/LIPIcs.FUN.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.FUN.2016.9
Analyzing and Comparing On-Line News Sources via (Two-Layer) Incremental Clustering

Authors: Francesco Cambi, Pierluigi Crescenzi, and Linda Pagli

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

Abstract
In this paper, we analyse the contents of the web site of two Italian press agencies and of four of the most popular Italian newspapers, in order to answer questions such as what are the most relevant news, what is the average life of news, and how much different are different sites. To this aim, we have developed a web-based application which hourly collects the articles in the main column of the six web sites, implements an incremental clustering algorithm for grouping the articles into news, and finally allows the user to see the answer to the above questions. We have also designed and implemented a two-layer modification of the incremental clustering algorithm and executed some preliminary experimental evaluation of this modification: it turns out that the two-layer clustering is extremely efficient in terms of time performances, and it has quite good performances in terms of precision and recall.
Cite as

Francesco Cambi, Pierluigi Crescenzi, and Linda Pagli. Analyzing and Comparing On-Line News Sources via (Two-Layer) Incremental Clustering. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{cambi_et_al:LIPIcs.FUN.2016.9,
  author =	{Cambi, Francesco and Crescenzi, Pierluigi and Pagli, Linda},
  title =	{{Analyzing and Comparing On-Line News Sources via (Two-Layer) Incremental Clustering}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{9:1--9: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.9},
  URN =		{urn:nbn:de:0030-drops-58777},
  doi =		{10.4230/LIPIcs.FUN.2016.9},
  annote =	{Keywords: text mining, incremental clustering, on-line news}
}
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