\input zb-basic
\input zb-ioport
\iteman{io-port 06014311}
\itemau{Poggi, Marcus; Sotelo, David}
\itemti{A linear time approximation algorithm for permutation flow shop scheduling.}
\itemso{Theor. Comput. Sci. 416, 87-94 (2012).}
\itemab
Summary: In the last 40 years, the permutation flow shop scheduling (PFS) problem with makespan minimization has been a central problem, known for its intractability, that has been well studied from both theoretical and practical aspects. The currently best performance ratio of a deterministic approximation algorithm for the PFS was recently presented by Nagarajan and Sviridenko, using a connection between the PFS and the longest increasing subsequence problem. In a different and independent way, this paper employs monotone subsequences in the approximation analysis techniques. To do this, an extension of the Erd\H{o}s-Szekeres theorem to weighted monotone subsequences is presented. The result is a simple deterministic algorithm for the PFS with a similar approximation guarantee, but a much lower time complexity.
\itemrv{~}
\itemcc{}
\itemut{permutation flow shop scheduling; approximation algorithms; Erd\H{o}s-Szekeres theorem}
\itemli{doi:10.1016/j.tcs.2011.10.013}
\end