Минимальное время завершения для взвешенной системы: различия между версиями

Также неисследованным остается направление неаппроксимируемости – имеется немало серьезных пробелов между известными гарантиями аппроксимации и коэффициентами сложности для различных классов задач. Например, известно, что задачи <math>R || \sum w_j C_j \;</math> и <math>R | r_j | \sum w_j C_j \;</math> являются сложно-аппроксимируемыми, однако лучшие известные алгоритмы, предложенные Скутеллой [11], имеют коэффициента аппроксимации 3/2 и 2, соответственно. Устранение этих пробелов представляет собой важную задачу.