Optimal Composition Ordering Problems for Piecewise Linear Functions

• Published in: Algorithmica 2018-07, Vol.80 (7), p.2134-2159
• Main Authors: Kawase, Yasushi, Makino, Kazuhisa, Seimi, Kento
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Linear functions; Mathematics of Computing; Permutations; Polynomials; Production scheduling; Special Issue on Algorithms and Computation; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-017-0397-y

In this paper, we introduce maximum composition ordering problems. The input is n real functions f 1 , ⋯ , f n : R → R and a constant c ∈ R . We consider two settings: total and partial compositions. The maximum total composition ordering problem is to compute a permutation σ : [ n ] → [ n ] which maximizes f σ ( n ) ∘ f σ ( n - 1 ) ∘ ⋯ ∘ f σ ( 1 ) ( c ) , where [ n ] = { 1 , ⋯ , n } . The maximum partial composition ordering problem is to compute a permutation σ : [ n ] → [ n ] and a nonnegative integer k ( 0 ≤ k ≤ n ) which maximize f σ ( k ) ∘ f σ ( k - 1 ) ∘ ⋯ ∘ f σ ( 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 total composition ordering problem can be solved in polynomial time if f i is of the form max { a i x + b i , d i , x } for some constants a i ( ≥ 0 ) , b i and d i . As a corollary, we show that the two-valued free-order secretary problem can be solved in polynomial time. 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.