Définir le problème d'optimisation - est-il np-complet?

L'ensemble est donné. Pour chaque élément , nous avons le poids et le coût . Le but est de trouver le sous-ensemble de taille qui maximise la fonction objectif suivante: . $S=\{e_1,\cdots,e_n\}$ $e_i$ $w_i>0$ $c_i>0$ $M$ $k$

\sum_{e_{i} \in M} w_{i} + \frac{\sum_{e_{i} \notin M} w_{i} c_{i}}{\sum_{e_{i} \notin M} c_{i}}

$\sum_{e_i\in M} w_i + \frac{\sum_{e_i\notin M} w_i c_i}{\sum_{e_i\notin M} c_i}$

Le problème est-il NP-difficile?

Puisque la fonction objectif semble étrange, il est utile d'expliquer une application de la fonction objectif.

Supposons que nous ayons n articles à et qu'il y ait copies de chaque objet dans notre inventaire. Nous avons quelques clients et ils sont intéressés par ces objets en proportion de leur poids , ce qui signifie que l'objet avec le plus grand est plus populaire. Nous avons un système de vente en ligne et nous devons répondre correctement aux demandes de nos clients. Nous ne pouvons pas reconnaître les objets par leurs formes (ils se ressemblent tous!). Mais nous avons un classificateur pour les trouver. Chaque classificateur peut être utilisé pour détecter des copies d'un objet. Nous visons à exécuter k classifier afin de maximiser la satisfaction de nos clients. $e_1$ $e_n$ $c_i$ $e_i$ $w_i$ $w_i$

PS: Il peut être utile de penser au cas où pour tout ; cependant, je ne suis pas sûr. [ J'avais tort à ce sujet! C'est en P par cette hypothèse ] $w_i c_i=p$ $i\leq n$

np-hardness optimization Nasooh
la source

Le bon terme est inférieur ou égal au plus grand poids d'un élément qui n'est pas en M. Donc, si vous avez un élément avec un poids important, il vaut mieux le mettre en M, plutôt que de le laisser se perdre. Donc, M devrait être composé des éléments avec les k plus grands poids. Droite?

zotachidil

Ce n'est pas correct, car les coûts sont également importants. Prenons l'exemple suivant:

Nasooh

w1 = 50, c1 = 80 - w2 = 40, c2 = 15 - w3 = 10, c3 = 5. Pour k égal à 1, choisir e2 est plus avantageux que e1.

Nasooh

Tu as raison. Hmm ...

zotachidil

Merci d'avoir essayé d'expliquer la motivation. Malheureusement, le lien entre votre explication et la fonction objective dans la question n'est toujours pas clair pour moi, mais je suppose que je dois être satisfait de l'explication actuelle pour garder la question dans une longueur raisonnable.

Tsuyoshi Ito du

Réponses:

La réponse ci-dessous observe qu'un cas particulier du problème est résoluble en temps polynomial. Cela ne répond pas entièrement à la question dans le message, mais peut donner un aperçu de ce qui pourrait être nécessaire pour une preuve de dureté NP, et peut susciter un intérêt supplémentaire pour le message ...

Observation. Le problème dans la publication a un algorithme qui, étant donné toute instance où chaque est un entier, s'exécute en polynôme temporel en et . $c_i$ $n$ $D = \sum_i c_i$

Croquis de preuve. Fixez toute entrée où et (WLOG) . En reformulant légèrement le problème, le but est de trouver de taille maximisant . $(S, w, c, K)$ $w,c\in\mathbb{R}_+^n$ $S=\{1,2,\ldots,n\}$ $M\subseteq S$ $K$ $\frac{\sum_{i\in M} w_i c_i}{\sum_{i\in M} c_i} - \sum_{i\in M} w_i$

Considérez le programme dynamique suivant. Pour tout entier avec , et , définissez La solution souhaitée est . $(d_1, d_2, k, m)$ $0\le d_1 \le d_2 \le D$ $0\le k \le K$ $k\le m\le n$

ϕ (d_{1}, d_{2}, k, m) = max {\sum_{i \in M} w_{i} (c_{i} / d_{1} - 1) : M \subseteq [m], | M | = k, \sum_{i \in M} c_{i} = d_{2}} .

$\textstyle\phi(d_1, d_2, k, m) = \max \Big\{ \sum_{i\in M} w_i (c_i / d_1 - 1) ~:~ M \subseteq [m],\, |M| = k, \, \sum_{i\in M} c_i = d_2\Big\}.$

max_{d} ϕ (d, d, K, n)

$\max_d \phi(d, d, K, n)$

En partitionnant les solutions possibles pour entre celles qui contiennent et celles qui n'en contiennent pas, nous obtenons la récurrence Nous quittons les cas limites comme un exercice. $\phi(d_1, d_2, k, m)$ $m$

ϕ (d_{1}, d_{2}, k, m) = max {\begin{cases} ϕ (d_{1}, d_{2} - c_{m}, k - 1, m - 1) + w_{m} (c_{m} / d_{1} - 1) \\ ϕ (d_{1}, d_{2}, k, m - 1) . \end{cases}

$\textstyle\phi(d_1, d_2, k, m) = \max\begin{cases} \phi(d_1, d_2 - c_m, k-1,m-1) + w_m(c_m/d_1-1) \\ \phi(d_1, d_2, k, m-1). \end{cases}$

Le nombre de sous - problèmes est , et pour chacun du côté droit de la récurrence peut être évaluée en temps constant, de sorte que les pistes de l' algorithme en temps polynomial en et . $O(n^2 D^2)$ $n$ $D$ $~~\Box$

Corollaire. À moins que P = NP, toute réduction montrant la dureté NP se réduira aux cas où n'est pas polynomial dans . $D$ $n$

Remarque. Sauf erreur, il existe également un PTAS pour le problème dans le message, basé sur l'arrondi des puis en utilisant la programmation dynamique. Cependant, l'existence d'un PTAS n'a aucune incidence directe sur la question de savoir si le problème est NP-difficile, comme demandé dans la publication. $w_i$

Je suis également curieux --- est-ce que quelqu'un sait si le cas spécial où (pour chaque ) a un algorithme poly-temps? (EDIT: c'est le cas, selon le commentaire de Willard Zhan, cela semble être optimisé en prenant pour contenir les plus grands éléments.) $w_i=c_i$ $i$ $M$ $k$

Neal Young
la source

Le cas de n'est-il pas la même chose que de minimiser , qui est optimisé lorsque compose du plus grand c'est?

w_{i} = c_{i}

$w_i=c_i$

(\sum_{i \neq j \notin M} w_{i} w_{j}) / (\sum_{i \notin M} w_{i})

$(\sum_{i\neq j\notin M}w_iw_j)/(\sum_{i\notin M} w_i)$

M

$M$

w_{i}

$w_i$

Willard Zhan

@WillardZhan, oui, cela semble juste.

Neal Young

-6

Vous vous interrogez sur la maximisation d'une fonction sans aucune restriction?

C'est vraiment simple. Si M est le plus grand ensemble, alors c'est la meilleure solution. Pas besoin de calculer quoi que ce soit.

Ce problème semble similaire au problème du sac à dos, qui est d'ailleurs NP.

Guillermo.
la source

La question dit, "le sous-ensemble M de taille k."

Tsuyoshi Ito du