New Bounds on Roller Coaster Permutations - Botler, Fábio; Netto, Bruno L. (Anais do Encontro de Teoria da Computação (ETC), 2021)
A roller coaster is a permutation π that maximizes the sum $\t(π) = \sum_{τ\in X(π)}\id(τ)$, where \(X(π)\) denotes the set of subsequences of \(π\) with cardinality at least \(3\); and \(\id(τ)\) denotes the number of maximal increasing or decreasing subsequences of contiguous numbers of \(τ\). We denote by \(\t_{\max}(n)\) the value \(\t(π)\), where \(π\) is a roller coaster of \(\{1,…,n\}\), for \(n≥ 3\). Precise values of \(\t_{\max}(n)\) for \(n≤ 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(π)$ for any given permutation $π$; and an Integer Linear Programming model to obtain roller coasters. As a result, we improve known lower bounds found in the literature for $n ≤ 40$.