This HTML5 document contains 64 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n9http://g.co/kg/m/
dbpedia-hehttp://he.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n19http://cseweb.ucsd.edu/~dasgupta/291-geom/
category-frhttp://fr.dbpedia.org/resource/Catégorie:
n12http://fr.dbpedia.org/resource/Modèle:
wikipedia-frhttp://fr.wikipedia.org/wiki/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n10http://www.nada.kth.se/~viggo/wwwcompendium/
owlhttp://www.w3.org/2002/07/owl#
n18http://ma-graph.org/entity/
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbrhttp://dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/

Statements

Subject Item
dbpedia-fr:K-centre
rdfs:label
Metric k-center K-centre
rdfs:comment
Le problème k-centre (k-center problem en anglais) est un problème d'optimisation combinatoire, une branche de l'algorithmique. Le problème peut se décrire de façon informelle ainsi : étant donné n villes, il faut ouvrir une caserne de pompiers dans k villes, tel que la distance entre chaque ville et la plus proche caserne soit minimisée.
owl:sameAs
dbpedia-he:בעיית_k_המרכזים n9:09k5mjk wikidata:Q6824324 dbr:Metric_k-center n18:17387949
dbo:wikiPageID
8761369
dbo:wikiPageRevisionID
178816691
dbo:wikiPageWikiLink
dbpedia-fr:Fonction_objectif dbpedia-fr:Gerhard_Woeginger dbpedia-fr:Problème_P_≟_NP dbpedia-fr:Université_de_Californie_à_San_Diego dbpedia-fr:Problème_NP-complet dbpedia-fr:Inégalité_triangulaire dbpedia-fr:Problème_de_décision dbpedia-fr:Théorie_des_graphes dbpedia-fr:Espace_euclidien dbpedia-fr:Graphe_planaire category-fr:Algorithme_de_partitionnement_de_données dbpedia-fr:Algorithme_glouton dbpedia-fr:Graphe_complet dbpedia-fr:Algorithmique category-fr:Problème_NP-complet dbpedia-fr:NP-difficile dbpedia-fr:APX_(complexité) dbpedia-fr:Ensemble_dominant dbpedia-fr:Marek_Karpinski dbpedia-fr:Problème_de_l'emplacement_d'installations dbpedia-fr:Problème_algorithmique dbpedia-fr:Partitionnement_de_données dbpedia-fr:Algorithme_d'approximation dbpedia-fr:K-médiane dbpedia-fr:K-moyennes dbpedia-fr:Espace_métrique dbpedia-fr:Optimisation_combinatoire dbpedia-fr:Complexité_en_temps dbpedia-fr:Schéma_d'approximation_en_temps_polynomial
dbo:wikiPageExternalLink
n10:node85.html n19:kcenter.pdf%7Ctitre=Lecture
dbo:wikiPageLength
10037
dct:subject
category-fr:Algorithme_de_partitionnement_de_données category-fr:Problème_NP-complet
prop-fr:wikiPageUsesTemplate
n12:, n12:Lien_web n12:Portail
prov:wasDerivedFrom
wikipedia-fr:K-centre?oldid=178816691&ns=0
prop-fr:année
2000 2013
prop-fr:auteur
Magnús Halldórsson dbpedia-fr:Marek_Karpinski Sanjoy Dasgupta Pierluigi Crescenzi dbpedia-fr:Gerhard_Woeginger Viggo Kann
prop-fr:langue
en
prop-fr:site
A compendium of NP optimization problems dbpedia-fr:Université_de_Californie_à_San_Diego
prop-fr:titre
Metric k-center
prop-fr:url
http://cseweb.ucsd.edu/~dasgupta/291-geom/kcenter.pdf|titre=Lecture 1 : Clustering in metric spaces n10:node85.html
foaf:isPrimaryTopicOf
wikipedia-fr:K-centre
dbo:abstract
Le problème k-centre (k-center problem en anglais) est un problème d'optimisation combinatoire, une branche de l'algorithmique. Le problème peut se décrire de façon informelle ainsi : étant donné n villes, il faut ouvrir une caserne de pompiers dans k villes, tel que la distance entre chaque ville et la plus proche caserne soit minimisée. De façon plus formelle, il s'agit, étant donné un ensemble de points V, de choisir un sous-ensemble de k points, appelés centres, tel que le maximum des distances des points de V au plus proche centre soit minimisée. Dans la majorité des cas on considère implicitement que l'espace est métrique, le problème s'exprime alors naturellement comme un problème sur un graphe dont les arêtes ont des poids respectant l'inégalité triangulaire. Ce problème est surtout étudié du point de vue de l'approximation. Il en existe plusieurs variantes, avec des métriques particulières, ou d'autres coûts à minimiser. Une application différente du placement d'installations, est le partitionnement de données (clustering).