Probleme du k-supplier

Probleme du k-supplier

Problème du k-supplier

Le problème du k-supplier minimal est un problème de théorie des graphes. Il s'apparente au problème du k-centre minimal mais en supprime la notion intuitive de centre.

En quelques mots, il s'agit de trouver sous contrainte un ensemble réparti de sommets « fournisseurs » tel que le reste des sommets du graphe, les « clients », aient dans leur voisinage un sommet « fournisseur » qui leur soit le plus proche possible. Rechercher un tel ensemble dans un graphe est un problème NP-complet.

K-supplier minimal

et vérifiant l'inégalité triangulaire.

  • Soit F \subset V et C \subset V tels que F \cap C = \emptyset et F \cup C = V
  • Solution :

un k-supplier minimal est S \subseteq F tel que

  • \sum_{v \in S} C(v) \leq k
  • \max_{v \in C} [\min_{s \in S} [W(s,v)]] est minimal

Références

  • Un algorithme d'approximation polynomial trouvant une solution de rapport constant a été énoncé dans A unified approach to approximation algorithms for bottleneck problems, (Journal of the Association for Computing Machinery) vol.33 n.3 (Jul 1986) 533-550.
Ce document provient de « Probl%C3%A8me du k-supplier ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Probleme du k-supplier de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Problème du k-supplier — Le problème du k supplier minimal est un problème de théorie des graphes. Il s apparente au problème du k centre minimal mais en supprime la notion intuitive de centre. En quelques mots, il s agit de trouver sous contrainte un ensemble réparti de …   Wikipédia en Français

  • Supplier Relationship Management — (SRM) bzw. Lieferantenbeziehungsmanagement umfasst die strategische Planung und zentrale Steuerung von Beziehungen eines Unternehmens zu seinen Lieferanten. Ziel des Einsatzes eines SRM Systems ist die enge Anbindung aller Lieferanten an das… …   Deutsch Wikipedia

  • K-supplier — Problème du k supplier Le problème du k supplier minimal est un problème de théorie des graphes. Il s apparente au problème du k centre minimal mais en supprime la notion intuitive de centre. En quelques mots, il s agit de trouver sous contrainte …   Wikipédia en Français

  • Lieferbeziehungsmanagement — Supplier Relationship Management (SRM) bzw. Lieferantenbeziehungsmanagement umfasst die strategische Planung und zentrale Steuerung von Beziehungen eines Unternehmens zu seinen Lieferanten. Ziel des Einsatzes eines SRM Systems ist die enge… …   Deutsch Wikipedia

  • GRÂCE — Le mot «grâce» et la réalité qu’il désigne ont une importance centrale dans la vie de l’humanité, et particulièrement dans l’histoire et la théologie chrétiennes. S’il est vrai que tout homme souffre d’un sentiment diffus et non expliqué de… …   Encyclopédie Universelle

  • Lieferantenbeziehungsmanagement — Das Lieferantenbeziehungsmanagement (als Fremdwort: Supplier Relationship Management, SRM) umfasst die strategische Planung und zentrale Steuerung von Beziehungen eines Unternehmens zu seinen Lieferanten. Ziel des Einsatzes eines SRM Systems ist… …   Deutsch Wikipedia

  • Oprah Winfrey — à la fête organisée pour son 50e anniversaire à l hôtel Bel Air, Los Angeles, le 29 janvier 2004. Données clés …   Wikipédia en Français

  • Wanderer (Unternehmen) — Wanderer Werke AG Rechtsform Aktiengesellschaft ISIN DE0007756009 Gründung …   Deutsch Wikipedia

  • Wanderer Werke — AG Unternehmensform Aktiengesellschaft ISIN …   Deutsch Wikipedia

  • Wanderer Werke AG — Unternehmensform Aktiengesellschaft ISIN …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”