Аноним

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

Материал из WEGA

Минимальное время завершения для взвешенной системы (посмотреть исходный код)

Версия от 19:08, 22 сентября 2016

263 байта убрано ,  22 сентября 2016
→‎Основные результаты
Строка 18: Строка 18:




Первым этапом преобразования на входе является геометрическое округление, при помощи которого длительность обработки и дата запуска преобразуются в степени значения <math>1 + \epsilon \;</math>, в результате чего общая эффективность снижается не более чем на <math>1 + \epsilon \;</math>. Что еще более важно, этот этап: (1) гарантирует небольшое количество различных значений длительности обработки и даты запуска; (2) позволяет разбивать время на геометрически возрастающие интервалы; и (3) выравнивает даты запуска относительно временных границ начала и конца интервалов. Все этим полезные свойства могут использоваться алгоритмом динамического программирования.
[[Файл:MWCT_table.png]]


Таблица 1. Основные результаты Афрати и др. [1]


Задача                  Время выполнения схем PTAS


Mn\T,wjq 0(2Р°М?)п+п|одп)
Первым этапом преобразования на входе является геометрическое округление, при помощи которого длительность обработки и дата запуска преобразуются в степени значения <math>1 + \epsilon \;</math>, в результате чего общая эффективность снижается не более чем на <math>1 + \epsilon \;</math>. Что еще более важно, этот этап: (1) гарантирует небольшое количество различных значений длительности обработки и даты запуска; (2) позволяет разбивать время на геометрически возрастающие интервалы; и (3) выравнивает даты запуска относительно временных границ начала и конца интервалов. Все этим полезные свойства могут использоваться алгоритмом динамического программирования.
PjrjjPwjCj O((m + 1 У0'* е >n + n log n)
Pjrj;pmtnjPwjCj 0(2P°Mi-)n+n|ogn)
Rmjrj jPwjCj O(f(m, ^)poly(n))
Rmjrj; pmtn jP wjCj O(f(m, j)n + nlogn)
RmjjPwjCj O(f(m, j)n + nlogn)
 
Таблица 1. Основные результаты Афрати и др. [ ]




Irina
4446

правок

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/11892