• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Глава

An Approximation Scheme for the Scheduling Problem with Guaranteed Absolute Error

P. 195-198.
Korenev P. S., Lazarev A. A.

In the paper, we consider the NP-hard total tardiness minimization on a single machine scheduling problem. We propose a metric for that problem and present a new polynomial approximation scheme based on search for the polynomially solvable instance which has a minimal distance in the metric from an initial instance.