Optimal Composition Ordering Problems for Piecewise Linear Functions

Abstract

In this paper, we introduce maximum composition ordering problems. The input is $n$ real functions $f_1,\dots ,f_n:\mathbb{R}\to \mathbb{R}$ and a constant $c\in \mathbb{R}$. We consider two settings: total and partial compositions. The maximum total composition ordering problem is to compute a permutation $\sigma :[n]\to [n]$ which maximizes $f_{\sigma (n)}\circ f_{\sigma (n-1)}\circ \cdots \circ f_{\sigma (1)}(c)$, where $[n]=\{1,\dots ,n\}$. The maximum partial composition ordering problem is to compute a permutation $\sigma :[n]\to [n]$ and a nonnegative integer $k(0\le k\le n)$ which maximize $f_{\sigma (k)}\circ f_{\sigma (k-1)}\circ \cdots \circ f_{\sigma (1)}(c)$. We propose $O(n\log n)$ time algorithms for the maximum total and partial composition ordering problems for monotone linear functions $f_i$, which generalize linear deterioration and shortening models for the time-dependent scheduling problem. We also show that the maximum partial composition ordering problem can be solved in polynomial time if $f_i$ is of form $\max \{a_{i}x+b_i,c_i\}$ for some constants $a_i(\ge 0)$, $b_i$ and $c_i$. We finally prove that there exists no constant-factor approximation algorithm for the problems, even if $f_i$'s are monotone, piecewise linear functions with at most two pieces, unless P=NP.

arXiv comment19 pages, 4 figures