A Vector-Sum Theorem and its Application to Improving Flow Shop Guarantees

We prove that if a closed polygonal path in R^d consists of a finite number of line segments of at most unit length, then it is possible to transpose the segments in such a way that the new polygonal path is contained in a ball of radius []. Using this result we give a near optimal algorithm for the NP-complete flow shop problem. The error of the algorithm cannot exceed a constant depending on the maximal execution time and the number of machines but not depending on the number of jobs. Our theorems improve earlier results of the same type by Belov and Stolin.