4446
правок
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) мНет описания правки |
||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 41: | Строка 41: | ||
Естественным образом возникает вопрос, является ли эта граница наилучшей. В одной из последующих работ Грэм [9] показал, что применение алгоритма LS к отсортированной последовательности заданий (в порядке невозрастания размеров) на самом деле дает улучшенную верхнюю границу коэффициента аппроксимации, равную <math>\frac{4}{3} - \frac{1}{3m}</math>. | Естественным образом возникает вопрос, является ли эта граница наилучшей. В одной из последующих работ Грэм [9] показал, что применение алгоритма LS к отсортированной последовательности заданий (в порядке невозрастания размеров) на самом деле дает улучшенную верхнюю границу коэффициента аппроксимации, равную <math>\frac{4}{3} - \frac{1}{3m}</math>. Аппроксимационную схему с полиномиальным временем выполнения предложили Хохбаум и Шмойс в работе [10]. Это лучший оффлайновый результат, на который можно было бы надеяться, поскольку, как известно, задача является NP-трудной в сильном смысле. | ||
Строка 50: | Строка 50: | ||
== Применение == | == Применение == | ||
В процессе последующего изучения алгоритмов | В процессе последующего изучения аппроксимационных алгоритмов (и в особенности онлайновых алгоритмов) при анализе многих алгоритмов планирования использовались методы, аналогичные приведенному выше доказательству. Далее приведены несколько вариантов задачи, в которых практически то же доказательство дает в результате точно такую же границу. | ||
Строка 69: | Строка 69: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Самая сложная нерешенная | Самая сложная нерешенная задача заключается в поиске наилучшего возможного коэффициента конкурентоспособности для этой базовой онлайновой задачи планирования. Разрыв между верхней и нижней границами невелик, но нахождение точной границы представляется очень трудным. Возможно, проще было бы найти наилучший возможный коэффициент конкурентоспособности для m = 4. Нижняя граница <math>\sqrt{3} \approx 1,732</math> была показана в работе [12], а известная на данный момент верхняя граница – 1,733 – в [3]. Таким образом, возможно, эта граница окажется равной <math>\sqrt{3}</math>. | ||
== Литература == | == Литература == |
правок