Алгоритмы аппроксимации полиномиального времени для машинного планирования: сколько осталось открытых задач?

В 1999 году Петра Шурман и Герхард Дж. Вёгингер опубликовали статью «Алгоритмы аппроксимации полиномиального времени для машинного планирования: десять открытых задач» . С тех пор, насколько мне известно, обзоры, которые касались бы одного и того же списка проблем, не появлялись. Таким образом, было бы здорово и полезно, если бы каждый из нас мог сделать такое резюме по некоторым из десяти открытых проблем и внести его здесь.

ds.algorithms approximation-algorithms open-problem approximation-hardness scheduling Dai Le
источник

PDF: Алгоритмы аппроксимации полиномиального времени для машинного планирования: десять открытых задач

Даниэль Апон

Я не думаю, что это нужно было сделать CW ...

Суреш Венкат

@Suresh Venkat: Как удалить CW?

Александр Бондаренко

К сожалению, нет способа превратить вики-вопрос сообщества в вопрос без CW. Добавление этой функции в механизм Stack Exchange запрашивается по адресу: meta.stackexchange.com/questions/6821/…

Tsuyoshi Ito,

Также см. Часто задаваемые вопросы о том, когда использовать тег CW: meta.cstheory.stackexchange.com/questions/225/…

Суреш Венкат

Минимизация времени выполнения на идентичных машинах с ограничением приоритета

Открытая Задача 1. Обеспечить результат inapproximability для . $4/3+\delta$ $P|prec|C_{max}$

Здесь первое, что приходит на ум, - это работа Ола Свенссона в этом году «Условная жесткость старшинства, ограниченное планирование на идентичных машинах». В своей статье Ола доказывает, что

«если проблему с одной машиной трудно приблизить с коэффициентом то рассматриваемую проблему с параллельной машиной, даже в случае единичного времени обработки, трудно приблизить с коэффициентом , где стремится к 0 как стремится к 0. " $2-\epsilon$ $2-\zeta$ $\zeta$ $\epsilon$

В 2008 году была опубликована статья «Планирование с ограничением приоритетов в · оптимальный », описывающий алгоритм дляс отношением производительности, упомянутым в его названии. Это улучшает алгоритм Коффмана-Грэма с оценкой $(2−\frac{7}{3p+1})$ $P|prec,p_j=1|C_{max}$ , где- количество машин. $2-\frac{2}{p}$ $p$

Статья Янсена и Солис-Обы «Алгоритмы аппроксимации для планирования заданий с ограничениями приоритета цепочки» содержит PTAS для , и, как следствие, для как частный случай первой проблемы. $Qm|chains|C_{max}$ $Pm|chains|C_{max}$

В этом году появилась статья Янсена и Солис-Обы («Журнал аппроксимации схем для планирования заданий с ограничениями цепочки приоритетов»), касающаяся PTAS для с фиксированным количеством рабочих мест в каждой цепочке и с постоянным количеством заданий в связанном компоненте каждого заказа. $P|chains|C_{max}$ $P|prec|C_{max}$

Минимизация времени выполнения на однородных машинах в условиях ограничения приоритета

$Qm|chains|C_{max}$

Минимизация времени выполнения при ограничениях приоритета с задержками связи

Минимизация Makespan на не связанных машинах

Максимизация минимизации в открытых магазинах

Максимизация минимизации в потоковых цехах

$2\sqrt{2}$

Максимизация минимизации в мастерских

$J||C_{max}$ $m$ $\mu$ $5/4+\delta$ $J||C_{max}$ $J||C_{max}$ $m$ машин до бесконечности.

$J2||C_{max}$ $\mu$ $\ne$

$J||C_{max}$ $O((\log lb)^{1-\epsilon})$ $NP\subseteq ZTIME(2^{\log n^{O(1/\epsilon)}})$ $J2||C_{max}$ $NP\subseteq DTIME(n^{O(\log n)})$

Общее время выполнения задания без ограничений по приоритету

Общее время выполнения задания с учетом ограничений приоритета

$1|prec|\sum C_j$ $1|prec|\sum w_jC_j$ $2−\epsilon$

В «Оптимальном тесте длинного кода с одним свободным битом» Бансал и Хот доказали, что это так, но предполагая новый вариант гипотезы об уникальных играх.

Критерии времени потока

$1|pmtn;r_j|\sum w_jF_j$ $P|pmtn;r_j|\sum F_j$

$O(1)$ $1|pmtn;r_j|\sum w_jF_j$ $O(1)$

$\Omega(\sqrt{\frac{\log P}{\log\log P}})$ $P|pmtn;r_j|\sum F_j$ $\Omega(\frac{\log P}{\log\log P})$

Александр Бондаренко
источник