Maximiser les poids des bords de somme

Je me demande si le problème suivant a un nom ou des résultats qui y sont liés.

$G = (V,w)$ $w(u,v)$ $u$ $v$ $u,v \in V$ $w(u,v) \in [-1,1]$

max_{S \subseteq V} \sum_{(u, v) : u \in S or v \in S} w (u, v)

$\max_{S \subseteq V} \sum_{(u,v) : u \in S\ \textrm{or}\ v\in S} w(u,v)$ Notez que je compte les bords à la fois à l'intérieur du sous-ensemble et à l'extérieur du sous-ensemble, ce qui distingue ce problème de la coupe maximale. Cependant, même si et sont tous deux dans , je ne veux compter l'arête qu'une seule fois (plutôt que deux fois), ce qui distingue l'objectif de la simple somme des degrés.

u

$u$

v

$v$

S

$S$

(u, v)

$(u,v)$

Notez que le problème est trivial si tous les poids de bord ne sont pas négatifs - prenez simplement le graphique entier!

reference-request graph-theory approximation-algorithms terminology approximation-hardness Aaron Roth
la source

Votre définition ne correspond pas à votre note plus tard sur le fait de ne pas compter les bords en double. Faites-vous la somme des paires ordonnées ou des sous-ensembles à 2 éléments? (ce dernier vous donnerait la propriété dont vous avez besoin, je pense)

Suresh Venkat

Une autre remarque: les seuls poids de bord NON comptés sont ceux à l'intérieur de V \ S. Êtes-vous intéressé par les résultats de dureté ou les approximations, car dans le premier cas, minimiser la somme des poids de bord à l'intérieur de S '= V \ S pourrait être le problème le plus naturel .

Suresh Venkat

@Suresh: La définition formelle de la question est correcte tant que le rapport d'approximation est concerné. Il donne juste exactement le double de ce que l'on attend des mots.

Tsuyoshi Ito le

@TsuyoshiIto: oh je vois, parce que les bords à travers la coupe sont également comptés deux fois.

Suresh Venkat

Le problème exact est NP-difficile car, comme Suresh l'a écrit dans son commentaire, le problème est équivalent à la programmation quadratique sans restriction {0,1}, qui est NP-difficile.

Tsuyoshi Ito

Réponses:

Pas vraiment une solution mais quelques observations.

C'est un cas particulier du problème suivant: étant donné un univers et une collection d'ensembles et une fonction de pondération , trouvez l'ensemble tel que soit maximisé (le poids d'un ensemble est le poids total de ses éléments). Votre problème correspond au cas où chaque élément de apparaît dans exactement deux ensembles (mais je ne sais pas comment exploiter cette restriction, bien que cela puisse aider). $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$

Il s'agit d'un problème de couverture: similaire à Max-k-Set-Cover, mais sans la restriction d'utiliser ensembles et avec des poids négatifs autorisés. L'approximation gourmande de Max-k-Set-Cover (à chaque sortie de sortie l'ensemble qui a le plus grand poids d'éléments découverts jusqu'à présent) génère une séquence d'ensembles de telle sorte que les premiers ensembles sont une approximation de la optimal (c'est donc une approximation simultanée pour tout ). Malheureusement, comme d'habitude, il y a un problème à l'analyser lorsque les poids peuvent être négatifs. L'observation de base de l'analyse de l'algorithme gourmand est que si est le premier ensemble qui est , alors ( $k$ $k$ $1 + 1/e$ $k$ $S_1$ $w(S_1) \geq OPT_k/k$ $OPT_k$ étant le poids maximal couvert par ensembles), car est inférieur à la somme des poids des ensembles dans la solution optimale, et chacun d'eux a un poids inférieur à . Cependant, avec des poids négatifs, il n'est plus vrai que soit inférieur à la somme des poids dans la solution optimale. En général, une union liée n'est plus vraie. $k$ $OPT_k$ $k$ $w(S_1)$ $OPT_k$

Sasho Nikolov
la source

FWIW, votre problème est difficile à approximer dans un facteur multiplicatif de pour tout . $n^{1-\epsilon}$ $\epsilon>0$

Nous montrons cela ci-dessous en donnant une réduction préservant l'approximation de l'ensemble indépendant, pour lequel la dureté de l'approximation est connue.

Réduction de l'ensemble indépendant

Soit le graphe non orienté une instance de l'ensemble indépendant. Laissez dénotant le degré de sommet dans . Laissez le nombre de sommets . $G=(V,E)$ $d_v$ $v$ $G$ $n$ $G$

Construisez le graphique pondéré par les bords partir de comme suit. Donnez à chaque arête en poids 1. Pour chaque sommet non isolé , ajoutez nouvelles arêtes, chacune avec un poids , à nouveaux sommets. Pour chaque sommet isolé , ajoutez une nouvelle arête de poids 1 à un nouveau sommet. $G'=(V',E')$ $G$ $E$ $v\in V$ $d_v-1$ $-1$ $d_v-1$ $v\in V$

(Remarque: chaque nouveau sommet (en mais pas ) a exactement un voisin, qui est en ) $G'$ $G$ $G$

Lemme. a un ensemble indépendant de taille si (en tant qu'instance de votre problème) a une solution de valeur au moins . $G$ $k$ $G'$ $k$

Preuve. Laissez être un ensemble indépendant dans . Alors, comme les sommets de sont indépendants de , la valeur de de (selon votre objectif) est $S$ $G$ $S$ $G'$ $S$ $G'$

\sum_{v \in S} d_{v} - (d_{v} - 1) = | S | .

$\sum_{v\in S} d_v - (d_v-1) ~=~ |S|.$

Inversement, soit une solution pour de valeur au moins . Sans perte de généralité, supposons que ne contienne pas de nouveaux sommets. (Chaque nouveau sommet est sur une seule arête . Si n'a pas été isolé dans , alors le poids de l'arête est , donc supprimer de augmente la valeur de Si a été isolé, alors le poids du bord est 1, donc supprimer de et ajouter maintient la valeur de ) $S$ $G'$ $k$ $S$ $v'$ $(v',v)$ $v$ $G$ $-1$ $v'$ $S$ $S$ $v$ $v'$ $S$ $v$ $S$

Sans perte de généralité, supposons que est un ensemble indépendant dans . (Sinon, soit une arête telle que et soient dans Le poids total des arêtes incidentes de dans est , donc le poids total de les arêtes incidentes autres que sont au plus nulles. Ainsi, supprimer de n'augmenterait pas la valeur de ) $S$ $G$ $(u,v)$ $u$ $v$ $S$ $v$ $G'$ $d_v - (d_v-1) = 1$ $v$ $(u,v)$ $v$ $S$ $S$

Maintenant, par le même calcul qu'au début de la preuve, la valeur de est. Il s'ensuit que . QED $S$ $|S|$ $|S| \ge k$

En passant, vous pourriez demander à la place une approximation additive , disons de ou . $O(n)$ $\epsilon m$

Il me semble possible que pour votre problème, même décider s'il existe une solution à valeur positive pourrait être difficile à NP.

Neal Young
la source