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

Глава

Algorithms for Solving Problems 1 | Σ Tj and Even-Odd Partition

P. 32-33.
Lazarev A. A., Kvaratskhelia A.

We consider NP-hard scheduling problem on a single machine minimizing total tardiness on a single machine. We present a number of polynomial and pseudo-polynomial algorithms for special cases of the problem. Based on these algorithms, we give the algorithm that solves Event-Odd Partition problem in pseudo-polynomial time. This algorithm for Partition problem can handle instances with non-integer parameters.