Сумма нескольких подмножеств

Проблема суммы множественного подмножества — это задача оптимизации в информатике и исследовании операций . Это обобщение проблемы суммы подмножества . Входными данными для задачи является мультимножество $S$ из n целых чисел и положительного целого числа m, представляющего количество подмножеств. Цель состоит в том, чтобы построить из входных целых чисел несколько m подмножеств. Проблема имеет несколько вариантов:

Максимальная сумма MSSP : для каждого подмножества j в 1,..., m существует емкость C _j . Цель состоит в том, чтобы сделать сумму всех подмножеств как можно большей, чтобы сумма в каждом подмножестве j не превышала C _j . ^[1]
Макс-мин MSSP (также называемый узким местом MSSP или BMSSP ): опять же, каждое подмножество имеет емкость, но теперь цель состоит в том, чтобы сделать сумму наименьшего подмножества как можно большей. ^[1]
Fair SSP : подмножества не имеют фиксированной мощности, но каждое подмножество принадлежит разным лицам. Полезность каждого человека равна сумме предметов в его/ее подмножествах. Цель состоит в том, чтобы создать подмножества, которые удовлетворяют заданному критерию справедливости, например максимальному и минимальному распределению элементов .

Макс-сумма и макс-мин MSSP

Когда m является переменной (часть входных данных), обе задачи являются строго NP-сложными за счет сокращения от 3-разбиения . Это означает, что у них нет полностью полиномиальной схемы аппроксимации (FPTAS), если только P = NP.

Даже когда m =2, проблемы не имеют FPTAS, если только P=NP. Это можно продемонстрировать с помощью сокращения равной мощности проблемы разделения (EPART):

Учитывая экземпляр a ₁ ,..., a _n EPART с целевой суммой T , создайте экземпляр 2 T + a ₁ , ..., 2 T + a _n MSSP с целевой суммой ( n +1) T для обоих подмножества.
Решение EPART состоит из двух частей, каждая из которых имеет / 2 элементов с суммой T. n Это соответствует оптимальному решению обоих вариантов MSSP: два подмножества с суммой ( n +1) T , которая является максимально возможной. Аналогично, каждое оптимальное решение MSSP соответствует решению EPART.
Любое неоптимальное решение MSSP оставляет нераспределенным хотя бы один элемент, поэтому его сумма составляет не более 2 нТ , а минимум - не более нТ . В обоих вариантах коэффициент аппроксимации не превышает $1-1/(n+1)$ .
Следовательно, для любого $\epsilon <1/(n+1)$ , любой алгоритм с коэффициентом аппроксимации $(1-\epsilon )$ необходимо найти оптимальное решение, если оно существует.
Если бы у нас был FPTAS, то у нас был бы алгоритм, например $\epsilon =1/(n+2)$ , с полиномом времени выполнения от n . Этот алгоритм можно использовать для решения EPART за полиномиальное от n время . Но это невозможно, если P=NP.

Известны следующие алгоритмы аппроксимации: ^[1]

Для максимальной суммы MSSP с переменной m :
- PTAS, работающий за время O( m+n ), когда $\epsilon$ фиксировано. Время выполнения как минимум экспоненциально $1/\epsilon ^{2}$ , и авторы считают это нецелесообразным.
- Более общий PTAS для случая, когда мощности подмножеств различны. ^[2]
- Алгоритм приближения 3/4, работающий за время O( m ²н ). ^[3]
Для макс-мин MSSP:
- С переменной m : приближение 2/3 за время O( n log n ). Лучшее приближение невозможно, если только P = NP (путем сокращения из 3-х разделов ).
- С фиксированным m : PTAS, работающий во времени. $O(n^{2m/\epsilon })$ .
- С фиксированным количеством различных входных значений: PTAS с использованием алгоритма Ленстры .

Проблема суммы справедливого подмножества

Задача о справедливой сумме подмножества ^[4] ( FSSP ) — это обобщение SSP, в котором после выбора подмножества его элементы распределяются между двумя или более агентами. Полезность каждого агента равна сумме весов выделенных ему объектов. Цель состоит в том, чтобы профиль полезности удовлетворял некоторому критерию справедливости, например правилу эгалитаризма или правилу пропорциональной справедливости . Два варианта проблемы:

Общие элементы : каждый элемент может быть назначен каждому агенту. Эта настройка аналогична справедливому распределению предметов с идентичными оценками (стоимость каждого предмета одинакова для всех агентов и равна весу предмета), однако существует дополнительное ограничение мощности на общий вес предметов. В качестве примера предположим, что веса элементов равны 3,5,7,9, а емкость равна 15. Тогда возможны следующие распределения: ( {3,5,7}, {} ); ( {3,5}, {7} ); ( {5}, {3,7} ); ( {5}, {9} ). Из этих распределений одно, удовлетворяющее критерию max-min, — это ( {3,5}, {7} ).
Отдельные предметы : для каждого агента существует отдельный набор предметов, которые могут быть выделены только ему/ей. Эта настройка актуальна, когда есть бюджет, который необходимо распределить по разным проектам, где каждый проект принадлежит уникальному агенту.

Оба варианта NP-сложные. Однако существуют алгоритмы псевдополиномиального времени для перебора всех оптимальных по Парето решений при наличии двух агентов: ^[5]

Для общих элементов: определите двумерный массив. $Q$ такой, что $Q(w_{1},w_{2})={\text{true}}$ тогда и только тогда, когда существует решение, дающее wi _вес общий агенту i . Можно во времени перечислить все возможные профили утилит. $O(n\cdot c^{2})$ где n — количество элементов, а c — максимальный размер элемента.
Для отдельных элементов: для каждого агента j определите динамический массив $Q_{j}$ , такой, что $Q_{j}(w)={\text{true}}$ тогда и только тогда, когда существует решение, дающее общий вес w агенту j . Каждый массив $Q_{j}$ можно построить отдельно, используя отдельные элементы агента j . Затем можно пройти два массива в противоположных направлениях и перечислить все распределения на границе Парето. Время выполнения $O(n\cdot c)$ .

Никосия, Пачичи и Пферши изучают цену справедливости , то есть соотношение между максимальной суммой полезностей и максимальной суммой полезностей в справедливом решении:

Для общих предметов: цена справедливости максимальной и минимальной справедливости не ограничена. Например, предположим, что есть четыре элемента со значениями 1, e , e , e для некоторого маленького e >0. Максимальная сумма равна 1 и достигается, если одному агенту дать предмет со стоимостью 1, а другому — ничего. Но распределение max-min дает каждому агенту значение не менее e , поэтому сумма должна быть не более 3 e . Следовательно, POF равен 1/(3e ) , что является неограниченным.
У Алисы есть два элемента со значениями 1 и e для некоторого маленького e >0. У Джорджа есть два элемента со значением e . Емкость равна 1. Максимальная сумма равна 1, ее можно получить, отдав Алисе предмет со стоимостью 1, а Джорджу ничего. Но распределение max-min дает обоим агентам значение e . Следовательно, POF равен 1/(2e ) , что является неограниченным.
Для отдельных позиций: цена справедливости максимальной и минимальной справедливости не ограничена. Например, предположим, что у Алисы есть два элемента со значениями 1 и e для некоторого маленького e >0. У Джорджа есть два элемента со значением e . Емкость равна 1. Максимальная сумма равна 1 - когда Алиса получает предмет со значением 1, а Джордж ничего не получает. Но распределение max-min дает обоим агентам значение e . Следовательно, POF равен 1/(2 e ), что является неограниченным.

В обоих случаях, если значение элемента ограничено некоторой константой a , то POF ограничен функцией a . ^[5]

Задача о нескольких рюкзаках

Задача о множественном рюкзаке (MKP) является обобщением как задачи MSSP о максимальной сумме, так и задачи о рюкзаке . В этой задаче имеется m рюкзаков и n предметов, каждый из которых имеет как ценность, так и вес. Цель состоит в том, чтобы упаковать как можно больше ценностей в m контейнеров так, чтобы общий вес в каждом контейнере был максимально равен его вместимости.

MSSP с максимальной суммой — это особый случай MKP, в котором стоимость каждого предмета равна его весу.
Задача о рюкзаке — это частный случай МКП, в котором m =1.
Проблема суммы подмножества — это частный случай MKP, в котором значение каждого элемента равно его весу и m = 1.

MKP имеет схему аппроксимации с полиномиальным временем . ^[6]

Ссылки

^ Jump up to: ^а ^б ^с Капрара, Альберто; Келлерер, Ганс; Пферши, Ульрих (1 февраля 2000 г.). «Проблема суммы множественных подмножеств» . SIAM Journal по оптимизации . 11 (2): 308–319. дои : 10.1137/S1052623498348481 . ISSN 1052-6234 .
^ Капрара, Альберто; Келлерер, Ганс; Пферши, Ульрих (29 февраля 2000 г.). «PTAS для решения задачи о сумме нескольких подмножеств с различной вместимостью рюкзаков» . Письма об обработке информации . 73 (3–4): 111–118. дои : 10.1016/S0020-0190(00)00010-7 . ISSN 0020-0190 .
^ Капрара, Альберто; Келлерер, Ганс; Пферши, Ульрих (1 марта 2003 г.). «Алгоритм приближения 3/4 для суммы нескольких подмножеств» . Журнал эвристики . 9 (2): 99–111. дои : 10.1023/А:1022584312032 . ISSN 1572-9397 . S2CID 1120180 .
^ Никосия, Гайя; Пасифичи, Андреа; Пферши, Ульрих (2015). Хофер, Мартин (ред.). «Краткое объявление: о проблеме суммы справедливого подмножества» . Алгоритмическая теория игр . Конспекты лекций по информатике. 9347 . Берлин, Гейдельберг: Springer: 309–311. дои : 10.1007/978-3-662-48433-3_28 . ISBN 978-3-662-48433-3 .
^ Jump up to: ^а ^б Никосия, Гайя; Пасифичи, Андреа; Пферши, Ульрих (16 марта 2017 г.). «Цена справедливости за распределение ограниченного ресурса» . Европейский журнал операционных исследований . 257 (3): 933–943. arXiv : 1508.05253 . дои : 10.1016/j.ejor.2016.08.013 . ISSN 0377-2217 . S2CID 14229329 .
^ Чандра Чекури и Санджив Кханна (2005). «ПТАС для решения задачи о нескольких рюкзаках». SIAM Journal по вычислительной технике . 35 (3): 713–728. CiteSeerX 10.1.1.226.3387 . дои : 10.1137/s0097539700382820 .

[:1-1] Jump up to: ^а ^б ^с Капрара, Альберто; Келлерер, Ганс; Пферши, Ульрих (1 февраля 2000 г.). «Проблема суммы множественных подмножеств» . SIAM Journal по оптимизации . 11 (2): 308–319. дои : 10.1137/S1052623498348481 . ISSN 1052-6234 .

[2] Капрара, Альберто; Келлерер, Ганс; Пферши, Ульрих (29 февраля 2000 г.). «PTAS для решения задачи о сумме нескольких подмножеств с различной вместимостью рюкзаков» . Письма об обработке информации . 73 (3–4): 111–118. дои : 10.1016/S0020-0190(00)00010-7 . ISSN 0020-0190 .

[3] Капрара, Альберто; Келлерер, Ганс; Пферши, Ульрих (1 марта 2003 г.). «Алгоритм приближения 3/4 для суммы нескольких подмножеств» . Журнал эвристики . 9 (2): 99–111. дои : 10.1023/А:1022584312032 . ISSN 1572-9397 . S2CID 1120180 .

[4] Никосия, Гайя; Пасифичи, Андреа; Пферши, Ульрих (2015). Хофер, Мартин (ред.). «Краткое объявление: о проблеме суммы справедливого подмножества» . Алгоритмическая теория игр . Конспекты лекций по информатике. 9347 . Берлин, Гейдельберг: Springer: 309–311. дои : 10.1007/978-3-662-48433-3_28 . ISBN 978-3-662-48433-3 .

[:2-5] Jump up to: ^а ^б Никосия, Гайя; Пасифичи, Андреа; Пферши, Ульрих (16 марта 2017 г.). «Цена справедливости за распределение ограниченного ресурса» . Европейский журнал операционных исследований . 257 (3): 933–943. arXiv : 1508.05253 . дои : 10.1016/j.ejor.2016.08.013 . ISSN 0377-2217 . S2CID 14229329 .

[6] Чандра Чекури и Санджив Кханна (2005). «ПТАС для решения задачи о нескольких рюкзаках». SIAM Journal по вычислительной технике . 35 (3): 713–728. CiteSeerX 10.1.1.226.3387 . дои : 10.1137/s0097539700382820 .

[1]

[2]

[3]

[4]

[5]

[6]