Максимальный вес «честного» соответствия

Меня интересует вариант соответствия максимального веса на графике, который я называю «Максимальное соответствие соответствия».

Предположим, что график заполнен (т.е. $E=V\times V$ ), Имеет четное число вершин, и что вес задается функцией прибыль . Для совпадающего обозначим через прибыль ребра которой сопоставляется. $p:{V\choose 2}\to \mathbb N$ $M$ $M(v)$ $v$

Соответствующее является точным совпадающим, если для любых двух вершин : $M$ $u,v\in V$

(\forall w \in V : p ({w, v}) \geq p ({w, u})) \to M (v) \geq M (u)

$(\forall w\in V:\ \ p(\{w,v\})\geq p(\{w,u\}))\to M(v)\geq M(u)$

То есть, если для любой вершины сопоставление с вершиной дает большую прибыль, чем сопоставление ее с вершиной , справедливого сопоставления должно хватить . $w\in V$ $w$ $v$ $u$ $M(v)\geq M(u)$

Можем ли мы найти максимальное соответствие по весу?

Интересный случай, когда график является двудольным, и справедливость применяется только к одной стороне, то есть предположим, что , и нам дана функция прибыли . $G=(L\cup R,L\times R)$ $p:L\times R\to \mathbb N$

Ярмарка Двудольные соответствия является соответствие в такое , что для любых двух вершин : $G$ $u,v\in L$

(\forall w \in R : p ({v, w}) \geq p ({u, w})) \to M (v) \geq M (u)

$(\forall w\in R:\ \ p(\{v,w\})\geq p(\{u,w\}))\to M(v)\geq M(u)$

Насколько быстро мы сможем найти подходящее двудольное соответствие с максимальным весом?

Мотивация для этой проблемы исходит из двудольного частного случая. Предположим, у вас есть работников и задач, и работник может приносить прибыль от работы . Проблема здесь заключается в том, чтобы разработать разумное решение (в каком-то смысле работники не будут чувствовать себя «оторванным»), в то же время максимизируя общие выплаты (здесь существует компромисс между силой механизма назначения и социальной выгодой). $n$ $m$ $i$ $p_{i,j}$ $j$

Если мы определим социальное обеспечение (или прибыль предприятия) от назначения рабочих мест на работу в качестве суммы прибыли.

Глядя на различные сценарии для силы назначителя работы, мы получаем следующие результаты:

Если нам разрешено назначать любого работника на любую работу, мы можем эффективно оптимизировать фабрику (просто найти соответствие по максимальному весу).
Если каждый работник выбирает задачу самостоятельно, предполагая, что его работа будет выбрана (для каждой работы может быть выбрана только одна работа), если он будет самым квалифицированным работником, который выбрал задачу, рабочие превратятся в «жадных» равновесие. Причина в том, что работник, который мог заработать больше всего ( ), выберет наиболее выгодную работу и так далее. По скорости аппроксимации жадного алгоритма сопоставления это должно дать 2-аппроксимацию максимально возможного социального благосостояния. $i=\mbox{argmax}_i \max_j p_{i,j}$

Я ищу что-то промежуточное. Предположим, мы могли бы назначить рабочих на рабочие места, но должны пообещать им, что ни один «менее квалифицированный» работник не зарабатывает больше, чем они.

Как мы можем найти максимальный вес, соответствующий обещающей «справедливости» сотрудникам эффективно?

ds.algorithms graph-algorithms np-hardness matching bipartite-graphs RB
источник

Тангенциально, для второго (двухстороннего) случая, кажется, легко построить примеры, где каждое «справедливое» совпадение дает прибыль первого рабочего 1, а остальные ноль, даже если существуют «несправедливые» совпадения, дающие прибыль первого рабочего и все остальные получают прибыль . Аналогично, примеры, в которых справедливое сопоставление с максимальным весом дает каждому работнику прибыль , даже если существуют несправедливые сопоставления, дающие прибыль каждого работника в .

1 - 2 ϵ

$1−2\epsilon$

1 - ϵ

$1−\epsilon$

2 / n

$2/n$

{1 - ϵ, 1 - 2 ϵ}

$\{1-\epsilon,1-2\epsilon\}$

Нил Янг

@NealYoung - правильно ли я предположить, что эти сценарии не могут существовать, если прибыль различна?

Это кажется стандартной проблемой в теории игр, когда неспособность различать альтернативы значительно снижает социальное благосостояние.

РБ

Ой, я забираю свой комментарий - я не уверен, что эти примеры в конце концов осуществимы!

Нил Янг

Я полагаю, что «максимальное соответствие нормального двудольного веса», как вы определили, является NP-трудным. Более того, определить наличие справедливого двустороннего сопоставления сложно с точки зрения NP.

Перед тем, как дать интуитивно понятный набросок, рассмотрим следующий небольшой пример. Возьмем где , . Возьмем , что для и , а для и . Тогда и эквивалентны в том смысле, что для всех , поэтому любое справедливое сопоставление должно давать и одинаковую прибыль. Следовательно, единственные честные совпадения либо совпадают $G'=(L, R, E'=L\times R)$ $L=\{a,b\}$ $R=\{c,d,e,f\}$ $p$ $p(u,w) = 0$ $u\in L$ $w\in\{c,d\}$ $p(u,w) = 1$ $u\in L$ $w\in\{e,f\}$ $a$ $b$ $p(a, w) = p(b, w)$ $w\in R$ $a$ $b$ $a$ и к и , или они соответствуют и к и . Используя этот вид гаджета, мы можем форсировать координацию ребер при сопоставлении. Это основа сокращения. $b$ $c$ $d$ $a$ $b$ $e$ $f$

Вот попытка доказательства. Это немного запутано. Вероятно, есть некоторые ошибки, но, надеюсь, любые ошибки можно исправить.

Лемма 1. Учитывая и как описано в задаче, определение, содержит ли справедливое совпадение, равно NP -жесткий. $G'=(L, R, E'=L\times R)$ $p:E'\rightarrow\mathbb{R}_+$ $G'$

Эскиз доказательства. Доказательством является сокращение от Независимого множества в кубических графах. Пусть - заданный экземпляр Независимого множества, где - кубический граф (каждая вершина имеет степень 3). Мы опишем, как построить граф и функцию прибыли , чтобы имел справедливое двустороннее соответствие, если и только если имеет независимый набор размера . $(G=(V,E),k)$ $G'$ $G'=(L, R, E'=L\times R)$ $p:E'\rightarrow\mathbb{R}_+$ $G'$ $G$ $k$

Вершины в будут приходить парами, называемыми партнерами . Аналогично для вершин в . Для каждой вершины обозначим партнера . Каждая вершина и ее партнер будут эквивалентны , что означает, что мы сделаем Следовательно, любое честное сопоставление должно присваивать одинаковую прибыль и . В дальнейшем мы будем использовать для обозначения значения . $L$ $R$ $v\in L\cup R$ $v'$ $v$ $\ell\in L$ $\ell'\in L$

p (ℓ, r) = p (ℓ^{'}, r) for all r \in R .

$p(\ell, r) = p(\ell', r) \text{ for all } r\in R.$

ℓ

$\ell$

ℓ^{'}

$\ell'$

π (ℓ, r)

$\pi(\ell, r)$

p (ℓ, r) = p (ℓ^{'}, r)

$p(\ell,r) = p(\ell', r)$

Кроме того, для каждой пары в и каждой пары партнеров в либо мы делаем либо мы делаем В первом случае мы говорим, что допускаем сопоставление и с и (поскольку при этом присваивается и такая же прибыль , как требуется). В последнем случае мы говорим, что мы предотвращаем и (обоих) с и $\ell$ $L$ $r, r'$ $R$

π (ℓ, r) = π (ℓ, r^{'})

$\pi(\ell, r) = \pi(\ell, r')$

π (ℓ, r) \neq π (ℓ, r^{'}) .

$\pi(\ell, r) \ne \pi(\ell, r').$

ℓ

$\ell$

ℓ^{'}

$\ell'$

r

$r$

r^{'}

$r'$

ℓ

$\ell$

ℓ^{'}

$\ell'$

ℓ

$\ell$

ℓ^{'}

$\ell'$

r

$r$

r^{'}

$r'$ (потому что при этом не будет присваиваться одинаковая прибыль и ).

ℓ

$\ell$

ℓ^{'}

$\ell'$

Поскольку данный граф кубический, он удовлетворяет условиюи любое независимое множество размера в инцидентно ровно ребер. Для простоты обозначения предположим, что . $G=(V,E)$ $3|V|=2|E|$ $I$ $k$ $G$ $3k$ $V=\{1,2,\ldots,n\}$

Для каждого ребра сделайте следующее. $\{i, j\}\in E$

Добавьте пару партнеров вершин для . $r(\{i,j\}), r'(\{i,j\})$ $R$
Для конечной точки , добавить пару вершин партнера в . Установите позволяя и сопоставляться с и . $i$ $\ell(i,j), \ell'(i,j)$ $L$
$π (ℓ (i, j), r ({i, j})) = π (ℓ (i, j), r^{'} ({i, j})) = i,$ $\pi(\ell(i,j), r(\{i,j\})) = \pi(\ell(i,j), r'(\{i,j\}))= i,$ $\ell(i,j)$ $\ell'(i,j)$ $r(\{i,j\})$ $r'(\{i,j\})$
Симметрично для другой конечной точки : добавьте еще одну пару вершин-партнеров в и установите что позволяет и быть сопоставленным с и . $j$ $\ell(j,i), \ell'(j,i)$ $L$
$π (ℓ (j, i), r ({i, j}) = π (ℓ (j, i), r^{'} ({i, j})) = j,$ $\pi(\ell(j,i), r(\{i,j\}) = \pi(\ell(j,i), r'(\{i,j\}))= j,$ $\ell(j,i)$ $\ell'(j,i)$ $r(\{i,j\})$ $r'(\{i,j\})$

Для всех и добавленных до сих пор, если пара явно не разрешена (см. Выше) для сопоставления с , тогда предотвратите совпадение, назначив и каждый по своему уникальному числу. $\ell\in L$ $r\in R$ $\ell, \ell'$ $r, r'$ $\pi(\ell, r)$ $\pi(\ell, r')$

Далее, добавьте пар наполнителя вершин . Для каждой вершины-заполнителя и каждой установите . $3(|V|-k)$ $R$ $r$ $\ell(i,j)\in L$ $\pi(\ell(i,j), r) = 0$

Наконец, добавьте две вершины и (партнеров) в , наряду с двумя вершинами и (также партнеров) в . Установите , позволяя сопоставлять и с и . Для любой другой вершины установите на некоторое уникальное число. (Следовательно, любое честное соответствие должно соответствовать и с и .) Для каждого $L_0$ $L'_0$ $L$ $R_0$ $R'_0$ $R$ $\pi(L_0, R_0) = \pi(L_0, R'_0) = 1$ $L_0$ $L'_0$ $R_0$ $R'_0$ $r\in R$ $\pi(L_0, r)$ $L_0$ $L'_0$ $R_0$ $R'_0$ $i\in V$ , для каждого инцидентного ребра , установите и . $\{i,j\}\in E$ $\pi(\ell(i,j), R_0) = i$ $\pi(\ell(i,j), R'_0) = |V|-i+1$

Это завершает сокращение. Чтобы закончить, мы докажем, что это правильно.

Сначала рассмотрим, для каких пар вершин последний доминирует над первым, т. $\ell(i,j),\ell(i',j')\in L$

(\forall r \in R) π (ℓ (i, j), r) \leq π (ℓ (i^{'}, j^{'}), r) .

$(\forall r\in R)~\pi(\ell(i,j),r) \le \pi(\ell(i',j'), r).$

С учетом прибыли, назначенной ребрам, падающим на и , это условие может быть выполнено только в том случае, если , и, проверяя определение для остальных ребер, условие является достаточным. Следовательно, сопоставление справедливо , если и только если она присваивает и к и , а также, для каждого , дает одинаковую прибыль для всех вершин в $R_0$ $R'_0$ $i=i'$ $\pi$ $i=i'$ $L_0$ $L'_0$ $R_0$ $R'_0$ $i\in V$

N (i) = {ℓ (i, j) : {i, j} \in E} \cup {ℓ^{'} (i, j) : {i, j} \in E} .

$N(i) = \{\ell(i,j) : \{i,j\}\in E\} \cup \{\ell'(i,j) : \{i,j\}\in E\}.$

Сначала предположим, что имеет независимое множество размера . Получить справедливое соответствие для из следующим образом. $G$ $I$ $k$ $G'$ $I$

Сопоставьте и с и . $L_0$ $L'_0$ $R_0$ $R'_0$

Для каждой вершины пусть это три ее инцидентных ребра. Для каждого ребра сопоставьте вершину и ее партнера с и . Это дает всем вершинам в прибыль . $i\in I$ $\{i,j_1\}, \{i,j_2\}, \{i,j_3\}$ $\{i, j_h\}$ $\ell(i,j_h)$ $\ell'(i,j_h)$ $r(\{i,j_h\})$ $r'(\{i, j_h\})$ $N(i)$ $i$

Для каждой из вершин для каждого из трех ребер инцидентных , сопоставим и его партнера некоторой уникальной паре вершин-заполнителей и ее партнера . Это дает всем вершинам в прибыль . $|V|-k$ $i\in V\setminus I$ $\{i,j\}$ $i$ $\ell(i,j)$ $\ell'(i,j)$ $r$ $r'$ $N(i)$ $0$

Следовательно, это соответствие справедливо.

Далее предположим , что имеет справедливое соответствия . $G'$ $M$

$M$ должны соответствовать и к и . Для каждого соответствие должно давать каждой из вершин в одинаковую прибыль. Для каждого его партнер также находится в . Таким образом, при проверке редукции прибыль каждой такой вершины должна быть либо (в этом случае все шесть вершин в соответствуют вершинам и их партнерам), либо нулю (в этом случае все шесть вершин из сопоставляются с вершинами-заполнителями в ). Позволять $L_0$ $L'_0$ $R_0$ $R'_0$ $i\in V$ $N(i)$ $\ell(i,j)\in N(i)$ $\ell'(i,j)$ $N(i)$ $i$ $N(i)$ $r(\{i,j\})$ $N(i)$ $R$ $I$ буду множеством вершин, для которых верен первый случай. Для каждого ребра каждая вершина и ее партнер совпадают с одной вершиной. Отсюда следует, что является независимым множеством. Поскольку число вершин-заполнителей равно , размер должен быть не менее . $\{i,j\}$ $r(\{i,j\})$ $I$ $6(|V|-k)$ $I$ $k$

КЭД (?)

Я думаю, что это в основном правильно, если немного запутанно. Дайте мне знать, если вы видите какие-либо ошибки или способ упростить доказательство.

Вышеуказанное сокращение предполагает, что можно взять, Если это нежелательно, то я думаю, что мы можем дополнить с помощьювершины-заполнители, присваивая прибыль 0 всем их ребрам, кроме ребер, и . Мы можем назначить прибыль последним ребрам, чтобы гарантировать, что вершины-заполнители не доминируют (или не доминируют) в любой другой вершине. $|R|>|L|$ $L$ $|R|-|L|$ $R_0$ $R'_0$

Нил Янг
источник

Максимальный вес «честного» соответствия

Ответы: