Минимизировать максимальную составляющую суммы векторов

Я хотел бы кое-что узнать об этой задаче оптимизации: для заданных неотрицательных целых чисел $a_{i,j,k}$ найдите функцию $f$ минимизирующую выражение

max_{k} \sum_{i} a_{i, f (i), k}

$\max_k \sum_i a_{i,f(i),k}$

Пример, использующий другую формулировку, может прояснить ситуацию: вам дан набор наборов векторов, таких как

{
    {(3, 0, 0, 0, 0), (1, 0, 2, 0, 0)},
    {(0, 1, 0, 0, 0), (0, 0, 0, 1, 0)},
    {(0, 0, 0, 2, 0), (0, 1, 0, 1, 0)}
}

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

(1, 0, 2, 0, 0) + (0, 1, 0, 0, 0) + (0, 1, 0, 1, 0) = (1, 1, 2, 1, 0)

с максимальным компонентом, равным 2, что здесь явно оптимально.

Мне интересно , если это хорошо известная проблема , и какие проблемы , специфичные приближенные методы решения доступны. Это должно быть быстро и легко программировать (без ЦЛПА решателя и т.д.). Нет точного решения не требуется , поскольку это всего лишь приближение реальной проблемы.

Я вижу, что я должен был добавить некоторые подробности о проблемах, которые меня интересуют:

$i \in \{0, 1, \ldots, 63\}$ , т. е. всегда есть 64 строки (при записи, как в приведенном выше примере).
$j \in \{0, 1\}$ , то есть, там уже только 2 векторов в ряд.
$k \in \{0, 1, \ldots, N-1\}$ , где (длина вектора) составляет от 10 до 1000. $N$

Более того, в каждой строке сумма элементов всех векторов одинакова, т.е.

\forall i, j, j^{'} : \sum_{k} a_{i, j, k} = \sum_{k} a_{i, j^{'}, k}

$\forall i, j, j':\quad \sum_k a_{i,j,k} = \sum_k a_{i,j',k}$

и сумма элементов вектора суммы меньше его длины, т.е.

\sum_{k} \sum_{i} a_{i, f (i), k} < N

$\sum_k \sum_i a_{i,f(i),k} < N$

algorithms optimization linear-programming maaartinus
источник

Нетрудно свести проблему с 3 разделами к вашей проблеме. Это означает, что ваша задача является NP-полной, даже если числа даны в унарном порядке, и это исключает один из распространенных подходов для алгоритма аппроксимации.

Цуёси Ито

Спасибо за исправления и спасибо @Tsuyoshi Ito за понимание. Если я правильно понимаю, ограничение в два вектора на строку (о чем я забыл заявить) лишает законной силы сокращение и может значительно облегчить проблему.

maaartinus

Вы правы, сокращение от проблемы с 3 разделами, о которой я думал, не работает, если в строке только два вектора.

Цуоши Ито

Таким образом , существует сочетания для сравнения?

j^{i}

$j^i$

Джейсон Клебан

@ uosɐſ: Точнее, есть возможных комбинаций, где - количество возможностей для а - количество возможностей для .

J^{I} = 2^{64}

$J^I=2^{64}$

J = 2

$J=2$

j

$j$

I = 64

$I=64$

i

$i$

Маартин

Ответы:

Снижение от 3sat к два вектора версии: дана формула, пусть индексные переменные, , и индексных оговорок. Пусть быть числом переменного раза оказываюсь положительно (если ) или отрицательно (если ) в пункте . OPT составляет менее тогда и только тогда формула выполнима (биекция очевидна). $i$ $j \in \{0,1\}$ $k$ $a_{i,j,k}$ $i$ $j = 0$ $j = 1$ $k$ $3$

Как бы атаковать эту проблему: большой поиск окрестностей. Начните с любым решением. Выбор строк в случайном порядке. Использование грубой силы , чтобы найти лучшее решение , где можно изменить только в тех строках-очень выполнимы даже для умеренных учитывая , что размер проблемы заключается строк. Повторение. $r$ $f$ $k$ $64$

привет моды
источник

Это красивое сокращение. Я не уверен, почему у этого нет никаких повышающих голосов. Во всяком случае, вот мой +1.

Цуоши Ито

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

f

$f$

Рафаэль

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

Тогда задача является NP-полной, даже если числа на входе даны в унарном виде. Это не ответ на ваш вопрос, потому что вы спрашиваете о приближении, но это нечто.

Определите проблему строго:

Экземпляр : n пар векторов a _i , b _i ∈ ℕ ^m ( i ∈ {1,…, n }) и K ∈ ℕ, все в унарном порядке.
Вопрос : Можем ли мы выбрать a _i или b _i для каждого i, чтобы сумма этих n векторов имела не более K в каждой координате?

Ниже приведена известная NP-полная проблема, называемая 3-разделом :

Экземпляр с 3 разделами : B ∈ ℕ и 3 k целых чисел c ₁ ,…, c _{3 k} между B / 4 и B / 2, исключающие, такие, что ∑ _{i = 1}^{3 k} c _i = kB , все в унарном порядке.
Вопрос : Можно ли разбить мультимножество { c ₁ ,…, c _{3 k} } на k мультимножеств S ₁ ,…, S _k так, чтобы сумма каждого S _j была равнаБ ?

Учитывая случай ( B ; c ₁ ,…, c _{3 k} ) задачи с 3 разделами, создайте пример вышеупомянутой проблемы следующим образом. Для каждого i = 1,…, 3 k и j = 1,…, k мы построим пару из 4 k -мерных векторов, представляющих выбор того, принадлежит ли c _i к S _j или нет:

Вектор, представляющий выбор « c _i ∈ S _j », имеет только одну ненулевую запись, которая равна ( k −1) c _i в j- й координате.
Вектор, представляющий выбор « c _i ∉ S _j », также имеет только одну ненулевую запись, которая является B в ( k + i ) -й координате.

Не трудно видеть , что экземпляр ( B , C ₁ , ..., с _{3 к} ) задачи 3-разбиения имеет решение тогда и только тогда , когда есть способ выбрать вектор из каждых из 3 к ² , построенным пары , так что все координаты суммы этих векторов не превосходит ( к -1) B . (На самом деле, когда это происходит, все координаты суммы равны ( k −1) B. ) Таким образом, это сокращение от задачи с 3-мя разбиениями до задачи выше.

До сих пор я игнорировал два дополнительных ограничения, указанных в конце вопроса, но оба легко применить, слегка изменив это сокращение. Условие, что сумма элементов каждого вектора равна, может быть применено путем добавления фиктивных координат, которые содержат только 0 или 1. Условие, что эта сумма меньше, чем измерение, может быть выполнено путем добавления фиктивных координат, которые содержат только 0.

Цуёси Ито
источник

N

$N$