Je suis invité à trouver une solution 2 approximative à ce problème:Problème de distribution d'annonces: une solution optimale?
Vous consultez pour un site de commerce électronique qui reçoit un grand nombre de visiteurs chaque jour. Pour chaque visiteur i, où i € {1, 2 ..... n}, le site a affecté une valeur v [i], représentant le revenu attendu pouvant être obtenu auprès de ce client.
Chaque visiteur i est montré un de m annonces possibles A1, A2 ..... Am comme ils entrer dans le site. Le site veut une sélection d'une annonce pour chaque client afin que que chaque annonce est vue, dans l'ensemble, par un ensemble de clients de poids total raisonnablement important.
Ainsi, étant donné une sélection d'une annonce pour chaque client, nous définissons la propagation de cette sélection pour le minimum, plus j = 1, 2 ..... m, du poids total de tous les clients qui ont été montrés ad Aj. Exemple: Supposons qu'il y ait six clients avec les valeurs 3, 4, 12, 2, 4, 6, et il y a m = 3 annonces. Alors, dans ce cas, on pourrait parvenir à une diffusion de 9 en montrant annonce A1 aux clients 1, 2, 4, annonce A2 au client 3 et annonce A3 à clients 5 et 6.
Le but ultime est pour trouver une sélection d'une annonce pour chaque client que maximise la propagation.
Malheureusement, ce problème d'optimisation est NP-difficile (vous n'avez pas à le prouver).
Ainsi, au lieu donner un algorithme polynomial qui se rapproche de la propagation maximale d'un facteur de 2.
La solution que je trouve est la suivante:
Order visitors values in descending order
Add the next visitor value (i.e. assign the visitor) to
the Ad with the current lowest total value
Repeat
Cette solution semble effectivement toujours trouver la solution optimale, ou je ne trouve tout simplement pas un contre-exemple. Pouvez-vous le trouver? Est-ce une solution non-polinomiale et je ne peux pas le voir?
Certaines informations sont manquantes. Affectez juste une annonce au client de valeur minimum et divisez le reste entre les autres. Par propagation, voulez-vous dire max-min? L'utilisation de la propagation a plus de sens dans ce cas ... Et le «poids total raisonnablement grand» n'est pas assez précis. –
C'est exactement ce qui est écrit dans mon manuel. Oui Par propagation, cela signifie max-min. – Mokuchan
Je vous suggère de modifier votre question pour refléter cela. –