Search Results

We first consider composition orderings for linear functions of one variable. Given n linear functions f_1,… ,f_n: ℝ → ℝ and a constant c ∈ ℝ, the objective is to find a permutation σ:[n] → [n] that minimizes/maximizes f_σ(n)∘⋯∘f_σ(1)(c), where [n] = {1, … , n}. It was first studied in the area of time-dependent scheduling, and known to be solvable in O(n log n) time if all functions are nondecreasing. In this paper, we present a complete characterization of optimal composition orderings for this case, by regarding linear functions as two-dimensional vectors. We also show the equivalence between local and global optimality in optimal composition orderings. Furthermore, by using the characterization above, we provide a fixed-parameter tractable (FPT) algorithm for the composition ordering problem with general linear functions, with respect to the number of decreasing linear functions. We next deal with matrix multiplication as a generalization of composition of linear functions. Given n matrices M₁,… , M_n ∈ ℝ^{m×m} and two vectors w,y ∈ ℝ^m, where m is a positive integer, the objective is to find a permutation σ:[n] → [n] that minimizes/maximizes w^⊤ M_σ(n) ⋯ M_σ(1) y. The matrix multiplication ordering problem has been studied in the context of max-plus algebra, but despite being a natural problem, it has not been explored in the conventional algebra to date. By extending the results for composition orderings for linear functions, we show that the matrix multiplication ordering problem with 2× 2 matrices is solvable in O(n log n) time if all the matrices are simultaneously triangularizable and have nonnegative determinants, and FPT with respect to the number of matrices with negative determinants, if all the matrices are simultaneously triangularizable. As the negative side, we prove that three possible natural generalizations are NP-hard. In addition, we derive the existing result for the minimum matrix multiplication ordering problem with 2 × 2 upper triangular matrices in max-plus algebra, which is an extension of the well-known Johnson’s rule for the two-machine flow shop scheduling, as a corollary of our result in the conventional algebra.