Suppose we are given a closed walk consisting of n steps in m-dimensio
nal space, each step having at most unit length (in a certain norm s).
We wish to include the walk into a given region of the space by reord
ering its steps. It turns out that our ability to solve this problem i
n polynomial time for certain regions of the space (such as the right
triangle or hexagon in the plane, the ball in R(m), etc.), enables us
to construct approximation algorithms with good performance guarantees
and polynomial running time for scheduling flow shops, job shops and
other problems of the type, known to be NP-hard. Some other geometric
methods are also to be spoken of subject to their application to sched
uling problems.