About: Metric k-center

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Metric k-center Goto Sponge NotDistinct Permalink

An Entity of Type : yago:State100024720, within Data Space : dbpedia.org associated with source document(s)
QRcode icon

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FMetric_k-center&graph=http%3A%2F%2Fdbpedia.org&graph=http%3A%2F%2Fdbpedia.org

In graph theory, the metric k-center or metric facility location problem is a combinatorial optimization problem studied in theoretical computer science. Given n cities with specified distances, one wants to build k warehouses in different cities and minimize the maximum distance of a city to a warehouse. In graph theory, this means finding a set of k vertices for which the largest distance of any point to its closest vertex in the k-set is minimum. The vertices must be in a metric space, providing a complete graph that satisfies the triangle inequality.

Attributes	Values
rdf:type	yago:WikicatApproximationAlgorithms yago:WikicatComputationalProblemsInGraphTheory yago:WikicatNP-completeProblems yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Event100029378 yago:Problem114410605 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity disease yago:Rule105846932 yago:State100024720
rdfs:label	K-centre (fr) Metric k-center (en)
rdfs:comment	In graph theory, the metric k-center or metric facility location problem is a combinatorial optimization problem studied in theoretical computer science. Given n cities with specified distances, one wants to build k warehouses in different cities and minimize the maximum distance of a city to a warehouse. In graph theory, this means finding a set of k vertices for which the largest distance of any point to its closest vertex in the k-set is minimum. The vertices must be in a metric space, providing a complete graph that satisfies the triangle inequality. (en) 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. (fr)
dcterms:subject	Approximation algorithms Combinatorial optimization NP-hard problems Computational problems in graph theory
Wikipage page ID	25385291 (xsd:integer)
Wikipage revision ID	1118824468 (xsd:integer)
Link from a Wikipage to another Wikipage	Approximation algorithm Independent set (graph theory) Approximation algorithms Combinatorial optimization Complete graph NP-complete NP-hard NP-hard problems Combinatorial optimization Theoretical computer science Triangle inequality Minimum k-cut Farthest-first traversal Graph theory Computational problems in graph theory Dominating set Greedy algorithm Metric space Vertex (graph theory) Facility location problem Metric (mathematics) NP-Hard Traveling salesman problem
sameAs	Metric k-center Metric k-center Metric k-center Metric k-center Metric k-center Metric k-center
dbp:wikiPageUsesTemplate	dbt:Citation dbt:Mvar dbt:Short_description
has 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). (fr) In graph theory, the metric k-center or metric facility location problem is a combinatorial optimization problem studied in theoretical computer science. Given n cities with specified distances, one wants to build k warehouses in different cities and minimize the maximum distance of a city to a warehouse. In graph theory, this means finding a set of k vertices for which the largest distance of any point to its closest vertex in the k-set is minimum. The vertices must be in a metric space, providing a complete graph that satisfies the triangle inequality. (en)
gold:hypernym	Problem
prov:wasDerivedFrom	wikipedia-en:Metric_k-center?oldid=1118824468&ns=0
page length (characters) of wiki page	10182 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Metric_k-center
is Link from a Wikipage to another Wikipage of	Farthest-first traversal List of NP-complete problems Teofilo F. Gonzalez Facility location problem Minimum k-center K-center
is Wikipage redirect of	Minimum k-center K-center
is foaf:primaryTopic of	wikipedia-en:Metric_k-center

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (62 GB total memory, 40 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software