%A Botler, Fábio
%A Netto, Bruno L.
%D 2021
%T New Bounds on Roller Coaster Permutations
%K
%X A roller coaster is a permutation \pi that maximizes the sum $\t(\pi) = \sum_{\tau\in X(\pi)}\id(\tau)$, where \(X(\pi)\) denotes the set of subsequences of \(\pi\) with cardinality at least \(3\); and \(\id(\tau)\) denotes the number of maximal increasing or decreasing subsequences of contiguous numbers of \(\tau\). We denote by \(\t_{\max}(n)\) the value \(\t(\pi)\), where \(\pi\) is a roller coaster of \(\{1,\ldots,n\}\), for \(n\geq 3\). Precise values of \(\t_{\max}(n)\) for \(n\leq 13\) were presented in \cite{AhmedTanbir}. In this paper, we explore the problem of computing lower bounds for \(\t_{\max}(n)\). More specifically, we present a cubic algorithm to compute $\t(\pi)$ for any given permutation $\pi$; and an Integer Linear Programming model to obtain roller coasters. As a result, we improve known lower bounds found in the literature for $n \leq 40$.
%U https://sol.sbc.org.br/index.php/etc/article/view/16378
%J Anais do Encontro de Teoria da Computação (ETC)
%0 Journal Article
%R 10.5753/etc.2021.16378
%P 50-53%@ 2595-6116
%8 2021-07-18