TY - JOUR
AU - Botler, Fábio
AU - Netto, Bruno L.
PY - 2021/07/18
TI - New Bounds on Roller Coaster Permutations
JF - Anais do Encontro de Teoria da Computação (ETC); 2021: Anais do VI Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2021.16378
KW -
N2 - 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$.
UR - https://sol.sbc.org.br/index.php/etc/article/view/16378