Многоканальное разбиение номеров

В информатике многоканальное разбиение чисел — это задача разбиения мультимножества чисел на фиксированное число подмножеств, так чтобы суммы подмножеств были максимально похожи. Впервые она была представлена ​​Рональдом Грэмом в 1969 году в контексте задачи планирования идентичных машин . [1] : раздел 5  Задача параметризуется положительным целым числом k и называется k -канальным разбиением чисел . [2] Входными данными для задачи является мультимножество S чисел (обычно целых), сумма которых равна k*T .

Связанная с этим задача принятия решения заключается в том, чтобы решить, можно ли разбить S на k подмножеств таким образом, чтобы сумма каждого подмножества была равна точно T. Существует также задача оптимизации : найти разбиение S на k подмножеств, чтобы суммы k были «настолько близки, насколько это возможно». Точная цель оптимизации может быть определена несколькими способами:

  • Минимизировать разницу между наибольшей и наименьшей суммой. Эта цель распространена в работах о многомерном разбиении чисел, а также в работах, исходящих из приложений физики. [2]
  • Минимизируйте наибольшую сумму. Эта цель эквивалентна одной цели для планирования идентичных машин . Имеется k идентичных процессоров, и каждое число в S представляет время, необходимое для завершения работы одного процессора. Цель состоит в том, чтобы распределить работы между процессорами таким образом, чтобы время выполнения (время завершения последней работы) было минимальным.
  • Максимизировать наименьшую сумму. Эта цель соответствует применению справедливого распределения элементов , в частности, максиминной доли . Она также появляется в задачах манипулирования голосованием, [3] и в последовательности действий по техническому обслуживанию модульных газотурбинных авиационных двигателей. [4] [5] Предположим, что есть некоторые k двигателей, которые должны работать как можно дольше. Для работы двигателя требуется определенная критическая деталь. Существует набор S деталей, каждая из которых имеет разный срок службы. Цель состоит в том, чтобы назначить детали двигателям таким образом, чтобы кратчайший срок службы двигателя был как можно больше.

Эти три целевые функции эквивалентны, когда k = 2, но они все различны, когда k ≥ 3. [6] [7]

Все эти задачи являются NP-трудными [ 8], но существуют различные алгоритмы, которые решают их эффективно во многих случаях.

Некоторые тесно связанные проблемы:

  • Задача о разбиении — частный случай многомерного разбиения чисел, в котором число подмножеств равно 2.
  • Задача о 3-х разбиениях — другая и более сложная задача, в которой количество подмножеств не считается фиксированным параметром, а определяется входными данными (количество множеств равно количеству целых чисел, делённому на 3).
  • Задача упаковки контейнеров — двойственная задача, в которой общая сумма в каждом подмножестве ограничена, но k — гибкое; цель — найти разбиение с наименьшим возможным k . Цели оптимизации тесно связаны: оптимальное количество контейнеров размером d не превышает k , если и только если оптимальный размер наибольшего подмножества в k -разбиении не превышает d . [9]
  • Задача планирования работы однородных машин — более общая задача, в которой разные процессоры могут иметь разную скорость.

Алгоритмы аппроксимации

Существуют различные алгоритмы, которые гарантированно получают приближение оптимального решения за полиномиальное время. Существуют различные алгоритмы приближения для различных целей.

Минимизация наибольшей суммы

Коэффициент аппроксимации в этом контексте — это наибольшая сумма в решении, возвращаемом алгоритмом, деленная на наибольшую сумму в оптимальном решении (коэффициент больше 1). Большинство алгоритмов ниже были разработаны для планирования идентичных машин .

  • Жадное разбиение чисел (также называемое « Наибольшее время обработки» в литературе по планированию) циклически перебирает числа и помещает каждое число в набор, текущая сумма которого наименьшая. Если числа не отсортированы, то время выполнения равно, а коэффициент аппроксимации не более. Сортировка чисел увеличивает время выполнения дои улучшает коэффициент аппроксимации до 7/6 при k = 2, ив общем случае. Если числа распределены равномерно в [0,1], то коэффициент аппроксимации не более почти наверняка , ив ожидании. О ( н ) {\displaystyle O(n)} 2 − 1 / к {\displaystyle 2-1/k} О ( н бревно ⁡ н ) {\displaystyle O(n\log {n})} 4 3 − 1 3 к = 4 к − 1 3 к {\displaystyle {\frac {4}{3}}-{\frac {1}{3k}}={\frac {4k-1}{3k}}} 1 + О ( бревно ⁡ бревно ⁡ н / н ) {\displaystyle 1+O(\log {\log {n}}/n)} 1 + О ( 1 / н ) {\displaystyle 1+O(1/n)}
  • Метод наибольшей разности (также называемый алгоритмом Кармаркара-Карпа ) сортирует числа в порядке убывания и многократно заменяет числа их разностями. Сложность выполнения составляет. В худшем случае его коэффициент аппроксимации аналогичен — не более 7/6 для k = 2 и не болеев общем случае. Однако в среднем случае он работает намного лучше, чем жадный алгоритм: для k = 2, когда числа распределены равномерно в [0,1], его коэффициент аппроксимации не болееожидаемого. Он также работает лучше в имитационных экспериментах. О ( н бревно ⁡ н ) {\displaystyle O(n\log {n})} 4 / 3 − 1 / 3 к {\displaystyle 4/3-1/3k} 1 + 1 / н Θ ( бревно ⁡ н ) {\displaystyle 1+1/n^{\Theta (\log {n})}}
  • Алгоритм Multifit использует бинарный поиск в сочетании с алгоритмом упаковки контейнеров . В худшем случае его время выполнения составляет не более 8/7 для k = 2 и не более 13/11 в общем случае.

Разработано несколько схем полиномиальной аппроксимации (PTAS):

  • Грэм [1] : раздел 6  представил следующий алгоритм. Для любого целого числа r>0 выберите r наибольших чисел в S и распределите их оптимально. Затем распределите оставшиеся числа произвольно. Этот алгоритм имеет отношение аппроксимации и работает за время . 1 + 1 − 1 / к 1 + ⌊ г / к ⌋ {\displaystyle 1+{\frac {1-1/k}{1+\lfloor r/k\rfloor }}} О ( 2 г н бревно ⁡ н ) {\displaystyle O(2^{r}n\log {n})}
  • Сахни [10] представил PTAS, который достигает (1+ε)OPT за время . Это FPTAS, если k фиксировано. Для k = 2 время выполнения улучшается до . Алгоритм использует технику, называемую интервальным разбиением . О ( н ⋅ ( н 2 / ϵ ) к − 1 ) {\displaystyle O(n\cdot (n^{2}/\epsilon )^{k-1})} О ( н 2 / ϵ ) {\displaystyle O(n^{2}/\epsilon)}
  • Хохбаум и Шмойс [9] представили следующие алгоритмы, которые работают даже тогда, когда k является частью входных данных.
    • Для любого r >0 алгоритм с коэффициентом аппроксимации не более (6/5+2 − r ) за время . О ( н ( г + бревно ⁡ н ) ) {\displaystyle O(n(r+\log {n}))}
    • Для любого r >0 алгоритм с коэффициентом аппроксимации не более (7/6+2 − r ) за время . О ( н ( г к 4 + бревно ⁡ н ) ) {\displaystyle O(n(rk^{4}+\log {n}))}
    • Для любого ε >0, алгоритм с коэффициентом аппроксимации не более (1+ε) за время . Это PTAS . О ( ( н / ε ) ( 1 / ε 2 ) ) {\displaystyle O((n/\varepsilon )^{(1/\varepsilon ^{2})})}

Максимизация наименьшей суммы

Коэффициент аппроксимации в данном контексте — это наименьшая сумма в решении, возвращаемом алгоритмом, деленная на наименьшую сумму в оптимальном решении (коэффициент меньше 1).

  • Для жадного разбиения чисел , если числа не отсортированы, то наихудшее приближение составляет 1/ k . [11] Сортировка чисел увеличивает приближение до 5/6, когда k = 2, и в общем случае оно плотное. [12] 3 к − 1 4 к − 2 {\displaystyle {\frac {3k-1}{4k-2}}}
  • Вёгингер [11] представил PTAS, который достигает фактора аппроксимации за время , где огромная константа, которая является экспоненциальной в требуемом факторе аппроксимации ε. Алгоритм использует алгоритм Ленстры для целочисленного линейного программирования . 1 − ε {\displaystyle 1-{\varepsilon}} О ( с ε н бревно ⁡ к ) {\displaystyle O(c_{\varepsilon }n\log {k})} с ε {\displaystyle c_ {\varepsilon }}
  • FPTAS Сахни [10] также служит этой цели.

Максимизация суммы произведений

Джин [13] изучает задачу, в которой цель состоит в максимизации суммы, по каждому набору i в 1,..., k , произведения чисел в наборе i . В более общем варианте каждый набор i может иметь вес w i , и цель состоит в максимизации взвешенной суммы произведений. Эта задача имеет точное решение, которое выполняется за время O( n 2 ).

PTAS для общих целевых функций

Пусть C i (для i между 1 и k ) будет суммой подмножества i в данном разделе. Вместо минимизации целевой функции max( C i ), можно минимизировать целевую функцию max( f ( C i )), где f — любая фиксированная функция. Аналогично можно минимизировать целевую функцию sum( f ( C i )), или максимизировать min(f( C i )), или максимизировать sum( f ( C i )). Алон, Азар, Вёгингер и Ядид [14] представили общие PTAS-ы (обобщающие PTAS-ы Санхи, Хохбаума и Шмойса, и Вёгингера) для этих четырех задач. Их алгоритм работает для любого f , которое удовлетворяет следующим двум условиям:

  1. Сильное условие непрерывности, называемое условием F* : для любого ε>0 существует δ>0 такое, что если | y - x |<δ x , то |f( y )-f( x )|<ε f ( x ).
  2. Выпуклость (для задач минимизации) или вогнутость (для задач максимизации).

Время выполнения их PTAS-s линейно по n (количество входов), но экспоненциально по точности аппроксимации. PTAS для минимизации суммы ( f ( C i )) основан на некоторых комбинаторных наблюдениях:

  1. Пусть L  := средняя сумма в одном подмножестве (1/ k — сумма всех входов). Если некоторый вход x равен по крайней мере L , то существует оптимальное разбиение, в котором одна часть содержит только x . Это следует из выпуклости f . Следовательно, вход может быть предварительно обработан путем назначения каждого такого входа уникальному подмножеству. После этой предварительной обработки можно предположить, что все входы меньше L .
  2. Существует оптимальное разбиение, в котором все суммы подмножеств строго находятся между L /2 и 2 L ( L /2 < C i < 2 L для всех i из 1,..., k ). В частности, разбиение, минимизирующее сумму квадратов C i 2 , среди всех оптимальных разбиений, удовлетворяет этим неравенствам.

PTAS использует технику округления входных данных . При наличии входной последовательности S = ​​( v 1 ,..., v n ) и положительного целого числа d округленная последовательность S # ( d ) определяется следующим образом:

  • Для любого v j > L/d последовательность S # ( d ) содержит вход v j # , который является v j , округленным до следующего целого числа, кратного L / d 2 . Обратите внимание, что v j ≤ v j # < v j + L / d 2 , и L/d 2 < v j / d , поэтому v j # < ( d +1) v j / d.
  • Кроме того, последовательность S # ( d ) содержит некоторые входы, равные L/d . Количество этих входов определяется таким образом, что сумма всех этих новых входов равна сумме всех входов в S # ( d ), которые не превышают L/d , округленной до следующего целого числа, кратного L/d (например, если сумма всех «коротких» входов в S составляет 51,3 L/d , то к S # ( d ) добавляется 52 новых входа L/d ).

В S # ( d ) все входы являются целыми кратными L / d 2 . Более того, два приведенных выше наблюдения справедливы и для S # ( d ):

  1. Пусть L # будет средней суммой в одном подмножестве (1/ k — сумма всех входов в S # ( d )). По построению L # не меньше L . Поскольку L само по себе является целым кратным L / d 2 , округление входов, меньших L, не может сделать их большими, чем L . Следовательно, все входы в S # ( d ) меньше L , и, следовательно, меньше, чем L # .
  2. Существует оптимальное разбиение S # ( d ), в котором все суммы подмножеств строго находятся между L # /2 и 2 L # . Следовательно, все подмножества содержат не более 2 d элементов (так как все входы в S # ( d ) не менее L / d ).

На основании этих наблюдений все входы в S # ( d ) имеют вид hL / d 2 , где h — целое число в диапазоне . Следовательно, вход может быть представлен как целочисленный вектор , где — количество входов hL / d 2 в S # ( d ). Более того, каждое подмножество может быть представлено как целочисленный вектор , где — количество входов hL / d 2 в подмножестве. Тогда сумма подмножества равна . Обозначим через , множество векторов с . Поскольку сумма элементов в таком векторе не превышает 2 d , общее количество этих элементов меньше , поэтому . ( г , г + 1 , … , г 2 ) {\displaystyle (d,d+1,\ldots ,d^{2})} н = ( н г , н г + 1 , … , н г 2 ) {\displaystyle \mathbf {n} =(n_{d},n_{d+1},\ldots ,n_{d^{2}})} н час {\displaystyle n_{h}} т = ( т г , т г + 1 , … , т г 2 ) {\displaystyle \mathbf {t} =(t_{d},t_{d+1},\ldots ,t_{d^{2}})} х час {\displaystyle x_{h}} С ( т ) = ∑ час = г г 2 т час ⋅ ( час Л / г 2 ) {\displaystyle C(\mathbf {t} )=\sum _{h=d}^{d^{2}}t_{h}\cdot (hL/d^{2})} Т {\displaystyle Т} т {\displaystyle \mathbf {т} } Л # / 2 < С ( т ) < 2 Л # {\displaystyle L^{\#}/2<C(\mathbf {t})<2L^{\#}} ( г 2 ) 2 г = г 4 г {\displaystyle {(d^{2})}^{2d}=d^{4d}} | Т | ≤ г 4 г {\displaystyle |T|\leq d^{4d}}

Существует два разных способа найти оптимальное решение для S # ( d ). Один способ использует динамическое программирование: его время выполнения — это полином, показатель степени которого зависит от d . Другой способ использует алгоритм Ленстры для целочисленного линейного программирования.

Решение динамического программирования

Определим как оптимальное (минимальное) значение целевой функции sum( f ( C i )), когда входной вектор равен и его необходимо разбить на k подмножеств, среди всех разбиений, в которых все суммы подмножеств находятся строго между L # /2 и 2 L # . В А Л ( к , н ) {\ displaystyle VAL (k, \ mathbf {n})} н = ( н г , н г + 1 , … , н г 2 ) {\displaystyle \mathbf {n} =(n_{d},n_{d+1},\ldots ,n_{d^{2}})}

Ее можно решить с помощью следующего рекуррентного соотношения :

  • В А Л ( 0 , 0 ) = 0 {\displaystyle VAL(0,\mathbf {0} )=0} - поскольку их объективная сумма пуста.
  • V A L ( 1 , n ) = f ( C ( n ) ) {\displaystyle VAL(1,\mathbf {n} )=f(C(\mathbf {n} ))} если - поскольку все входы должны быть отнесены к одному подмножеству, то их сумма равна . L # / 2 < C ( n ) ) < 2 L # {\displaystyle L^{\#}/2<C(\mathbf {n} ))<2L^{\#}} C ( n ) {\displaystyle C(\mathbf {n} )}
  • V A L ( 1 , n ) = ∞ {\displaystyle VAL(1,\mathbf {n} )=\infty } в противном случае - поскольку мы не рассматриваем оптимальные решения за пределами этого диапазона.
  • V A L ( k , n ) = min t ≤ n , t ∈ T [ f ( C ( t ) ) + V A L ( k − 1 , n − t ) ] {\displaystyle VAL(k,\mathbf {n} )=\min _{\mathbf {t} \leq \mathbf {n} ,\mathbf {t} \in T}[f(C(\mathbf {t} ))+VAL(k-1,\mathbf {n} -\mathbf {t} )]} для всех : мы проверяем все варианты для k -го подмножества и объединяем его с оптимальным разбиением остатка на k -1 подмножеств. k ≥ 2 {\displaystyle k\geq 2}

Для каждого k и n рекуррентное отношение требует проверки не более векторов. Общее количество векторов n для проверки не более , где n — исходное количество входов. Следовательно, время выполнения алгоритма динамического программирования составляет . Оно линейно по n для любого фиксированного d . | T | {\displaystyle |T|} n d 2 {\displaystyle n^{d^{2}}} O ( k ⋅ n d 2 ⋅ d 4 d ) {\displaystyle O(k\cdot n^{d^{2}}\cdot d^{4d})}

Решение целочисленного линейного программирования

Для каждого вектора t в T введите переменную x t , обозначающую количество подмножеств с этой конфигурацией. Минимизация суммы ( f ( C i )) может быть достигнута путем решения следующего ILP:

  • Свернуть ∑ t ∈ T x t ⋅ f ( C ( t ) ) {\displaystyle \sum _{\mathbf {t} \in T}x_{\mathbf {t} }\cdot f(C(\mathbf {t} ))}
  • при условии (общее количество подмножеств) ∑ t ∈ T x t = k {\displaystyle \sum _{\mathbf {t} \in T}x_{\mathbf {t} }=k}
  • и (общий вектор входов) ∑ t ∈ T x t ⋅ t = n {\displaystyle \sum _{\mathbf {t} \in T}x_{\mathbf {t} }\cdot \mathbf {t} =\mathbf {n} }
  • и . x t ≥ 0 {\displaystyle x_{\mathbf {t} }\geq 0}

Число переменных не более , а число уравнений - оба являются константами, не зависящими от n , k . Поэтому можно использовать алгоритм Ленстры . Его время выполнения экспоненциально в размерности ( ), но полиномиально в двоичном представлении коэффициентов, которые находятся в O(log( n )). Построение самого ILP занимает время O( n ). d 4 d {\displaystyle d^{4d}} d 4 d + d 2 − d + 2 {\displaystyle d^{4d}+d^{2}-d+2} d 4 d {\displaystyle d^{4d}}

Преобразование решения из округленного в исходный экземпляр

Следующие леммы связывают разбиения округленного экземпляра S # ( d ) и исходного экземпляра S .

  • Для каждого разбиения S с суммами C i существует разбиение S # ( d ) с суммами C i # , где . C i − L d ≤ C i # ≤ d + 1 d C i + L d {\displaystyle C_{i}-{\frac {L}{d}}\leq C_{i}^{\#}\leq {\frac {d+1}{d}}C_{i}+{\frac {L}{d}}}
  • Для каждого разбиения S # ( d ) с суммами C i # существует разбиение S с суммами C i , где , и его можно найти за время O( n ). d d + 1 C i # − 2 L d ≤ C i ≤ C i # + L d {\displaystyle {\frac {d}{d+1}}C_{i}^{\#}-2{\frac {L}{d}}\leq C_{i}\leq C_{i}^{\#}+{\frac {L}{d}}}

При заданной точности аппроксимации ε>0 пусть δ>0 будет константой, соответствующей ε/3, существование которой гарантируется условием F*. Пусть . Можно показать, что преобразованное разбиение S имеет общую стоимость не более , поэтому коэффициент аппроксимации равен 1+ε. d := ⌈ 5 / δ ⌉ {\displaystyle d:=\lceil 5/\delta \rceil } ( 1 + ϵ 3 ) ⋅ O P T ≤ ( 1 + ϵ ) ⋅ O P T {\displaystyle (1+{\frac {\epsilon }{3}})\cdot OPT\leq (1+\epsilon )\cdot OPT}

Отсутствие PTAS для некоторых целевых функций

В отличие от приведенного выше результата, если мы возьмем f( x ) = 2 x , или f( x )=( x -1) 2 , то не существует PTAS для минимизации суммы ( f ( C i )) если только P=NP . [14] : Раздел 4  Обратите внимание, что эти f( x ) являются выпуклыми, но они не удовлетворяют условию F* выше. Доказательство проводится путем сведения из задачи разбиения .

Точные алгоритмы

Существуют точные алгоритмы , которые всегда находят оптимальное разбиение. Поскольку задача NP-трудная, такие алгоритмы могут занять экспоненциальное время в общем случае, но могут быть практически применимы в определенных случаях.

  • Разбиение псевдополиномиального времени числа занимает O ( n ( k − 1) m k − 1 ) памяти, где m — наибольшее число на входе. Это практично только когда k = 2 или когда k = 3 и входы являются небольшими целыми числами. [15]
  • Полный жадный алгоритм (CGA) рассматривает все разбиения, строя k - арное дерево . Каждый уровень в дереве соответствует входному числу, где корень соответствует наибольшему числу, уровень ниже — следующему по величине числу и т. д. Каждая из k ветвей соответствует разному набору, в который может быть помещен текущий номер. Обход дерева в глубину-сначала требует только O( n ) пространства, но может занять O( k n ) времени. Время выполнения можно улучшить, используя жадную эвристику: на каждом уровне сначала разрабатывайте ветвь, в которой текущий номер помещается в набор с наименьшей суммой. Этот алгоритм сначала находит решение, найденное жадным разбиением чисел , но затем переходит к поиску лучших решений.
  • Полный алгоритм Кармаркара-Карпа (CKK) рассматривает все разбиения, строя дерево степени . Каждый уровень соответствует паре k -кортежей, а каждая из ветвей соответствует разному способу объединения этих k -кортежей. Этот алгоритм сначала находит решение, найденное методом наибольшей разности , но затем переходит к поиску лучших решений. Для k = 2 и k = 3 CKK работает существенно быстрее, чем CGA на случайных экземплярах. Преимущество CKK над CGA намного больше в последнем случае (когда существует равное разбиение) и может быть на несколько порядков величины. На практике при k = 2 задачи произвольного размера могут быть решены с помощью CKK, если числа имеют не более 12 значащих цифр s; при k = 3 — не более 6 значащих цифр. [16] CKK также может работать как алгоритм, действующий в любое время : он сначала находит решение KK, а затем находит все лучшие решения по мере того, как позволяет время (возможно, требуя экспоненциального времени для достижения оптимальности в худших случаях). [17] При k ≥ 4 CKK становится намного медленнее, а CGA работает лучше. k ! {\displaystyle k!} k ! {\displaystyle k!}
  • Корф, Шрайбер и Моффитт представили гибридные алгоритмы, объединяющие CKK, CGA и другие методы из задачи подмножества суммы и задачи упаковки контейнеров для достижения еще лучшей производительности. Их журнальная статья 2018 года [18] суммирует работы из нескольких предыдущих конференционных докладов:
    • Рекурсивное разбиение чисел (RNP) [15] использует CKK для k = 2, но при k > 2 оно рекурсивно разбивает S на подмножества и разбивает k пополам.
    • Гибридное рекурсивное разбиение чисел (HRNP). [19]
    • Улучшено заполнение корзины. [20]
    • Улучшенные стратегии поиска. [21]
    • Алгоритм нескольких машин. [22]
    • Кэшированное итеративное ослабление (CIW). [23]
    • Последовательное разбиение . [24]

Сокращение упаковки в контейнеры

Проблема упаковки контейнеров имеет много быстрых решателей. Решатель BP может быть использован для поиска оптимального разбиения чисел. [25] Идея заключается в использовании бинарного поиска для поиска оптимального makespan. Для инициализации бинарного поиска нам нужны нижняя и верхняя границы:

  • Некоторые нижние границы makespan таковы: (сумма S )/ k — среднее значение на подмножество, s 1 — наибольшее число в S и s k + s k+1 — размер ячейки в оптимальном разбиении только наибольших k +1 чисел.
  • Некоторые верхние границы могут быть достигнуты путем применения эвристических алгоритмов, таких как жадный алгоритм или КК.

Задайте нижнюю и верхнюю границу, запустите решатель BP с размером интервала middle := (lower+upper)/2.

  • Если результат содержит более k ячеек, то оптимальный диапазон выполнения должен быть больше: установите значение от нижнего до среднего и повторите.
  • Если результат содержит не более k ячеек, то оптимальный интервал выполнения может быть меньше, установлен выше среднего и повторен.

Варианты

В задаче разбиения сбалансированных чисел существуют ограничения на количество элементов, которые могут быть выделены для каждого подмножества (они называются ограничениями мощности ).

Другой вариант – многомерное разбиение чисел . [26]

Приложения

Одно из применений проблемы разделения — манипулирование выборами . Предположим, что есть три кандидата (A, B и C). Один кандидат должен быть избран с использованием правила голосования с правом вето, т. е. каждый избиратель накладывает вето на одного кандидата, и побеждает кандидат с наименьшим количеством вето. Если коалиция хочет обеспечить избрание C, она должна разделить свои вето между A и B так, чтобы максимизировать наименьшее количество вето, которое получает каждый из них. Если голоса взвешены, то проблему можно свести к проблеме разделения, и, таким образом, ее можно эффективно решить с помощью CKK. Для k = 2 то же самое верно для любого другого правила голосования, основанного на подсчете очков. Однако для k > 2 и других правил голосования требуются некоторые другие методы. [3]

Реализации

  • Python: пакет prtpy содержит код для различных алгоритмов разбиения чисел и упаковки в контейнеры.

Ссылки

  1. ^ ab Graham, Ron L. (1969-03-01). «Границы аномалий многопроцессорной синхронизации». Журнал SIAM по прикладной математике . 17 (2): 416–429. doi :10.1137/0117039. ISSN  0036-1399.
  2. ^ ab Mertens, Stephan (2006), "The Easiest Hard Problem: Number Partitioning", в Allon Percus; Gabriel Istrate; Cristopher Moore (ред.), Computational difficulty and Statistics Physics , Oxford University Press US, стр. 125, arXiv : cond-mat/0310317 , Bibcode : 2003cond.mat.10317M, ISBN 978-0-19-517737-4
  3. ^ ab Walsh, Toby (2009-07-11). «Где действительно сложные проблемы манипуляции? Фазовый переход в манипулировании правилом вето» (PDF) . Написано в Пасадене, Калифорния, США. Труды Двадцать первой международной совместной конференции по искусственному интеллекту . Сан-Франциско, Калифорния, США: Morgan Kaufmann Publishers Inc. стр. 324–329. Архивировано (PDF) из оригинала 2020-07-10 . Получено 2021-10-05 .
  4. ^ Фризен, Д.К.; Дойермейер, Б.Л. (1981-02-01). «Анализ жадных решений для задачи последовательности замены деталей». Математика исследования операций . 6 (1): 74–87. doi :10.1287/moor.6.1.74. ISSN  0364-765X.
  5. ^ Дойермейер, Брайан Л.; Фризен, Дональд К.; Лэнгстон, Майкл А. (1982-06-01). «Планирование для максимизации минимального времени завершения работы процессора в многопроцессорной системе». Журнал SIAM по алгебраическим и дискретным методам . 3 (2): 190–196. doi :10.1137/0603019. ISSN  0196-5212.
  6. ^ Корф, Ричард Эрл (2010-08-25). "Целевые функции для многомерного разбиения чисел". Третий ежегодный симпозиум по комбинаторному поиску . 1 : 71–72. doi : 10.1609/socs.v1i1.18172 . S2CID  45875088.
  7. ^ Уолтер, Рико (2013-01-01). «Сравнение минимального времени завершения двух эвристик планирования с наибольшим первым». Central European Journal of Operations Research . 21 (1): 125–139. doi :10.1007/s10100-011-0217-4. ISSN  1613-9178. S2CID  17222989.
  8. ^ Гэри, Майкл Р.; Джонсон, Дэвид С. (1979). Компьютеры и неразрешимость: Руководство по теории NP-полноты . WH Freeman and Company. стр. 238. ISBN 978-0716710448.
  9. ^ ab Hochbaum, Dorit S.; Shmoys, David B. (1987-01-01). «Использование алгоритмов двойного приближения для решения задач планирования: теоретические и практические результаты». Journal of the ACM . 34 (1): 144–162. doi : 10.1145/7531.7535 . ISSN  0004-5411. S2CID  9739129.
  10. ^ ab Sahni, Sartaj K. (1976-01-01). «Алгоритмы планирования независимых задач». Журнал ACM . 23 (1): 116–127. doi : 10.1145/321921.321934 . ISSN  0004-5411. S2CID  10956951.
  11. ^ ab Woeginger, Gerhard J. (1997-05-01). «Схема аппроксимации полиномиального времени для максимизации минимального времени завершения работы машины». Operations Research Letters . 20 (4): 149–154. doi :10.1016/S0167-6377(96)00055-7. ISSN  0167-6377.
  12. ^ Чирик, Янош; Келлерер, Ханс; Вёгингер, Герхард (1992-06-01). «Точная граница LPT для максимизации минимального времени завершения». Operations Research Letters . 11 (5): 281–287. doi :10.1016/0167-6377(92)90004-M. ISSN  0167-6377.
  13. ^ Jin, Kai (2017). «Оптимальное разбиение, которое максимизирует взвешенную сумму продуктов». В Xiao, Mingyu; Rosamond, Frances (ред.). Frontiers in Algorithmics . Lecture Notes in Computer Science. Vol. 10336. Cham: Springer International Publishing. pp. 127–138. doi :10.1007/978-3-319-59605-1_12. ISBN 978-3-319-59605-1.
  14. ^ ab Алон, Нога; Азар, Йосси; Вёгингер, Герхард Дж.; Ядид, Тал (1998). «Аппроксимационные схемы для планирования на параллельных машинах». Журнал планирования . 1 (1): 55–66. doi :10.1002/(SICI)1099-1425(199806)1:1<55::AID-JOS2>3.0.CO;2-J. ISSN  1099-1425.
  15. ^ ab Корф, Ричард Э. (2009). Многоканальное разбиение чисел (PDF) . IJCAI .
  16. ^ Корф, Ричард Э. (1995-08-20). «От приближенных к оптимальным решениям: пример разбиения чисел». Труды 14-й Международной объединенной конференции по искусственному интеллекту — Том 1. IJCAI'95. Монреаль, Квебек, Канада: Morgan Kaufmann Publishers Inc.: 266–272. ISBN 978-1-55860-363-9.
  17. ^ Корф, Ричард Э. (1998-12-01). «Полный алгоритм разбиения чисел на части в любое время». Искусственный интеллект . 106 (2): 181–203. doi : 10.1016/S0004-3702(98)00086-1 . ISSN  0004-3702.
  18. ^ Шрайбер, Итан Л.; Корф, Ричард Э.; Моффитт, Майкл Д. (2018-07-25). «Оптимальное многоканальное разбиение чисел». Журнал ACM . 65 (4): 24:1–24:61. doi : 10.1145/3184400 . ISSN  0004-5411. S2CID  63854223.
  19. ^ Корф, Ричард Э. (2011-07-16). "Гибридный рекурсивный многоходовой алгоритм разбиения чисел". Труды Двадцать второй международной совместной конференции по искусственному интеллекту - Том Том первый . IJCAI'11. Барселона, Каталония, Испания: AAAI Press: 591–596. ISBN 978-1-57735-513-7.
  20. ^ Шрайбер, Итан Л.; Корф, Ричард Э. (2013-08-03). "Улучшенное завершение бинов для оптимальной упаковки бинов и разбиения чисел" (PDF) . Труды Двадцать третьей Международной совместной конференции по искусственному интеллекту . IJCAI '13. Пекин, Китай: AAAI Press: 651–658. ISBN 978-1-57735-633-2.
  21. ^ Моффитт, Майкл Д. (2013-08-03). "Стратегии поиска оптимального многоканального разбиения чисел" (PDF) . Труды Двадцать третьей международной совместной конференции по искусственному интеллекту . IJCAI '13. Пекин, Китай: AAAI Press: 623–629. ISBN 978-1-57735-633-2.
  22. ^ Корф, Ричард; Шрайбер, Итан (2013-06-02). «Оптимальное планирование небольшого количества идентичных параллельных машин». Труды Международной конференции по автоматизированному планированию и составлению расписаний . 23 : 144–152. doi : 10.1609/icaps.v23i1.13544 . ISSN  2334-0843. S2CID  12458816.
  23. ^ Шрайбер, Итан Л.; Корф, Ричард Э. (2014-07-27). «Кэшированное итеративное ослабление для оптимального многостороннего разбиения чисел». Труды конференции AAAI по искусственному интеллекту . AAAI'14. 28. Квебек, Квебек, Канада: AAAI Press: 2738–2744. doi : 10.1609/aaai.v28i1.9122 . S2CID  8594071.
  24. ^ Ричард Э. Корф, Итан Л. Шрайбер и Майкл Д. Моффитт (2014). «Оптимальное последовательное многоканальное разбиение чисел» (PDF) .{{cite web}}: CS1 maint: multiple names: authors list (link)
  25. ^ Шрайбер, Итан Л.; Корф, Ричард Э. (2013-08-03). «Улучшенное завершение бинов для оптимальной упаковки бинов и разбиения чисел». Труды Двадцать третьей Международной совместной конференции по искусственному интеллекту . IJCAI '13. Пекин, Китай: AAAI Press: 651–658. ISBN 978-1-57735-633-2.
  26. ^ Pop, Petrică C.; Matei, Oliviu (2013-11-01). «Подход меметического алгоритма для решения многомерной задачи многомерного разбиения чисел». Applied Mathematical Modelling . 37 (22): 9191–9202. doi : 10.1016/j.apm.2013.03.075 . ISSN  0307-904X.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Multiway_number_partitioning&oldid=1199108428"