K-supplier
- 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
et 
tels que 
et 
- Solution :
un k-supplier minimal est 
tel que
![\max_{v \in C} [\min_{s \in S} [W(s,v)]]](/pictures/frwiki/102/fd46035d53edc21496e1f5b521036c5b.png)
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.
Catégorie : Algorithmique
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article K-supplier de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
supplier — [ syplije ] v. tr. <conjug. : 7> • 1360; réfect. étym. de souploier (XIIe), souplier (XIIIe); du lat. supplicare « se plier (sur les genoux) », avec infl. de ploier (ployer) ♦ Prier (qqn) en demandant qqch. comme une grâce, avec une… … Encyclopédie Universelle
Supplier evaluation — is a term used in business and refers to the process of evaluating and approving potential suppliers by factual and measurable assessment. The purpose of supplier evaluation is to ensure a portfolio of best in class suppliers is available for use … Wikipedia
Supplier convergence — is a term used to describe the ongoing trend of companies offering a combination of services or products that were previously supplied by separate companies. It is not to be confused with product convergence, where one product combines and… … Wikipedia
Supplier enablement — is the process of electronically connecting suppliers (or other trading partners) to a company s supply chain. Supplier enablement is achieved when suppliers of goods and services are connected to a company s back office systems to exchange… … Wikipedia
supplier — sup‧pli‧er [səˈplaɪə ǁ ər] noun [countable] COMMERCE a company that provides a particular type of product: supplier of • Microsoft is the world s largest supplier of PC software. • With California s orange crop halved, local suppliers have had to … Financial and business terms
Supplier diversity — is a business program that encourages the use of previously underutilized minority owned vendors as suppliers. It is not directly correlated with supply chain diversification, although utilizing more vendors may enhance supply chain… … Wikipedia
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
Supplier — Sup*pli er, n. One who supplies. [1913 Webster] … The Collaborative International Dictionary of English
Supplier Furnished Equipment — (SFE)In aviation, when an aircraft is made and delivered it will come with all agreed SFE equipment. The opposite of SFE is buyer furnished equipment BFE, which is purchased by the buyer and given to the aircraft manufacturer to be installed… … Wikipedia
Supplier — may refer to:*Manufacturer, uses tools and labor to make things for sale *Processor (manufacturing), converts a product from one form to another *Packager (manufacturing), encloses products for distribution, storage, sale, and use *Distributor… … Wikipedia
supplier — I noun caterer, chandler, commissary, contractor, furnisher, giver, merchant, provider, provisioner, purveyor, seller, steward, trader, victualer II index contributor (giver), materialman Burton s Legal Thesaurus. Wil … Law dictionary
