Максимизация суммарных весов ребер

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

Пусть - взвешенный граф, где обозначает вес ребра между и , и для всех , . Задача состоит в том, чтобы найти подмножество вершин, которое максимизирует сумму весов смежных с ними ребер: Обратите внимание, что я подсчитываю ребра как внутри подмножества, так и вне его, что отличает эту проблему от max-cut. Однако, даже если и u, и v находятся в S , я хочу только посчитать ребро (u, v)$G = (V,w)$$w(u,v)$$u$$v$$u,v \in V$$w(u,v) \in [-1,1]$

Обратите внимание, что проблема тривиальна, если все веса ребер неотрицательны - просто возьмите весь граф!

Не совсем решение, но некоторые наблюдения.

Это частный случай следующей задачи: заданный юниверс и набор множеств и весовая функция , найдите множество такое, что максимизируется (вес набора - это общий вес его элементов). Ваша проблема соответствует случаю, когда каждый элемент появляется ровно в двух наборах (но я не уверен, как использовать это ограничение, хотя это может помочь).$U = \{1, \ldots, m\}$$S_1, \ldots, S_n \subseteq U$$w:U \rightarrow [-1, 1]$$I \subseteq [n]$$w(\bigcup_{i \in I}{S_i})$$U$

Это проблема покрытия: аналогично Max-k-Set-Cover, но без ограничения на использование наборов и с разрешенными отрицательными весами. Жадная аппроксимация Max-k-Set-Cover (на каждом шаге выводить набор, который имеет наибольший вес из непокрытых элементов на данный момент) выводит последовательность наборов, так что первые наборов являются приближением к оптимальный (так что это одновременное приближение для всех ). К сожалению, как обычно, существует проблема с анализом, когда веса могут быть отрицательными. Основное наблюдение за анализом жадного алгоритма состоит в том, что если является первым выходным набором, то ($k$$k$$1 + 1/e$$k$$S_1$$w(S_1) \geq OPT_k/k$$OPT_k$является максимальным весом, охватываемым наборами), поскольку меньше суммы весов множеств в оптимальном решении, и каждый из них имеет вес, меньший чем . Однако с отрицательными весами больше не верно, что меньше, чем сумма весов в оптимальном решении. В общем, объединение больше не верно.$k$$OPT_k$$k$$w(S_1)$$OPT_k$

Кстати, вашу проблему трудно аппроксимировать с мультипликативным коэффициентом для любого .$n^{1-\epsilon}$$\epsilon>0$

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

Сокращение от независимого набора

Пусть неориентированный граф будет экземпляром независимого множества. Пусть обозначит степень вершины в . Пусть -число вершин в .$G=(V,E)$$d_v$$v$$G$$n$$G$

Построить гранично-взвешенный граф из следующим образом. Задайте каждое ребро в весе 1. Для каждой неизолированной вершины добавьте новые ребра , каждый с весом , в новые вершины . Для каждой изолированной вершины добавьте одно новое ребро веса 1 к новой вершине.$G'=(V',E')$$G$$E$$v\in V$$d_v-1$$-1$$d_v-1$$v\in V$

(Примечание: каждая новая вершина (в но не в ) имеет ровно одного соседа, который находится в )$G'$$G$$G$

Лемма. имеет независимый набор размера если (как пример вашей проблемы) имеет решение со значением не менее .$G$$k$$G'$$k$

Доказательство. Пусть любое независимое множество в . Тогда, поскольку вершины в независимы в , значение в (согласно вашей цели) равно $S$$G$$S$$G'$$S$$G'$

Наоборот, пусть - решение для со значением не менее . Без ограничения общности предположим, что содержит новых вершин. (Каждая новая вершина находится на одном ребре . Если не было изолировано в , то вес ребра равен , поэтому удаление из увеличивает значение Если было выделено, тогда вес ребра равен 1, поэтому удаление из и добавление поддерживает значение )$S$$G'$$k$$S$$v'$$(v',v)$$v$$G$$-1$$v'$$S$$S$$v$$v'$$S$$v$$S$

Без ограничения общности будем считать , что является независимым множеством в . (В противном случае, пусть будет ребром таким, что и находятся в Общий вес падающих ребер в равен , поэтому общий вес Число инцидентных ребер, отличных от , не больше нуля. Таким образом, удаление из не приведет к увеличению значения )$S$$G$$(u,v)$$u$$v$$S$$v$$G'$$d_v - (d_v-1) = 1$$v$$(u,v)$$v$$S$$S$

Теперь, согласно тому же расчету, что и в начале доказательства, значение равно, Отсюда следует, что . QED$S$$|S|$$|S| \ge k$

Кроме того, вы можете вместо этого попросить аддитивное приближение, скажем, или . $O(n)$$\epsilon m$

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