Problème 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

Soit $k \in \N^+$

Soit le graphe complet $G = (V, E)$ valué par

$C : V \rightarrow \N^+$

$W : E \rightarrow \N^+$

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.

Une formulation du problème et quelques liens

Catégorie :
Algorithmique

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

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

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 … 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

Dictionnaires et Encyclopédies sur 'Academic'

Problème du k-supplier

K-supplier minimal

Références

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Problème du k-supplier

K-supplier minimal

Références

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link