1 Search Results for "Serafin, Radoslaw"

Document

DOI: 10.4230/LIPIcs.STACS.2019.30

Fast and Longest Rollercoasters

Authors: Paweł Gawrychowski, Florin Manea, and Radosław Serafin

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract

For k >= 3, a k-rollercoaster is a sequence of numbers whose every maximal contiguous subsequence, that is increasing or decreasing, has length at least k; 3-rollercoasters are called simply rollercoasters. Given a sequence of distinct real numbers, we are interested in computing its maximum-length (not necessarily contiguous) subsequence that is a k-rollercoaster. Biedl et al. (2018) have shown that each sequence of n distinct real numbers contains a rollercoaster of length at least ceil[n/2] for n>7, and that a longest rollercoaster contained in such a sequence can be computed in O(n log n)-time (or faster, in O(n log log n) time, when the input sequence is a permutation of {1,...,n}). They have also shown that every sequence of n >=slant (k-1)^2+1 distinct real numbers contains a k-rollercoaster of length at least n/(2(k-1)) - 3k/2, and gave an O(nk log n)-time (respectively, O(n k log log n)-time) algorithm computing a longest k-rollercoaster in a sequence of length n (respectively, a permutation of {1,...,n}). In this paper, we give an O(nk^2)-time algorithm computing the length of a longest k-rollercoaster contained in a sequence of n distinct real numbers; hence, for constant k, our algorithm computes the length of a longest k-rollercoaster in optimal linear time. The algorithm can be easily adapted to output the respective k-rollercoaster. In particular, this improves the results of Biedl et al. (2018), by showing that a longest rollercoaster can be computed in optimal linear time. We also present an algorithm computing the length of a longest k-rollercoaster in O(n log^2 n)-time, that is, subquadratic even for large values of k <= n. Again, the rollercoaster can be easily retrieved. Finally, we show an Omega(n log k) lower bound for the number of comparisons in any comparison-based algorithm computing the length of a longest k-rollercoaster.

Cite as

Paweł Gawrychowski, Florin Manea, and Radosław Serafin. Fast and Longest Rollercoasters. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gawrychowski_et_al:LIPIcs.STACS.2019.30,
  author =	{Gawrychowski, Pawe{\l} and Manea, Florin and Serafin, Rados{\l}aw},
  title =	{{Fast and Longest Rollercoasters}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.30},
  URN =		{urn:nbn:de:0030-drops-102694},
  doi =		{10.4230/LIPIcs.STACS.2019.30},
  annote =	{Keywords: sequences, alternating runs, patterns in permutations}
}

Refine by Author
1 Gawrychowski, Paweł
1 Manea, Florin
1 Serafin, Radosław

Refine by Classification
1 Theory of computation → Data structures design and analysis
1 Theory of computation → Design and analysis of algorithms

Refine by Keyword
1 alternating runs
1 patterns in permutations
1 sequences

Refine by Type
1 document

Refine by Publication Year
1 2019

1 Search Results for "Serafin, Radoslaw"

Fast and Longest Rollercoasters

Abstract

Cite as

Thanks for your feedback!

Could not send message