Composition Orderings for Linear Functions and Matrix Multiplication Orderings

We consider composition orderings for linear functions of one variable. Given n linear functions f1,dots,fn and a constant c, the objective is to find a permutation σ that minimizes/maximizes fσ(n)circdotscirc fσ(1)(c). It was first studied in the area of time-dependent scheduling, and known to be solvable in O(nlog 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 several interesting properties on optimal composition orderings such as the equivalence between local and global optimality. Furthermore, by using the characterization above, we provide a fixed-parameter tractable (FPT) algorithm for the composition ordering problem for general linear functions, with respect to the number of decreasing linear functions. We next deal with matrix multiplication orderings as a generalization of composition of linear functions. Given n matrices M1,dots,Mn∈ℝm× m and two vectors w,y∈ℝm, where m denotes a positive integer, the objective is to find a permutation σ that minimizes/maximizes w^top Mσ(n)dots Mσ(1) y. The problem is also viewed as a generalization of flow shop scheduling through a limit. By this extension, we show that the multiplication ordering problem for 2× 2 matrices is solvable in O(nlog 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 finally prove that three possible natural generalizations are NP-hard: 1) when m=2, 2) when m≥ 3, and 3) the target version of the problem.