About: K-approximation of k-hitting set

An Entity of Type: Rule105846932, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

In computer science, k-approximation of k-hitting set is an approximation algorithm for weighted hitting set. The input is a collection S of subsets of some universe T and a mapping W from T to non-negative numbers called the weights of the elements of T. In k-hitting set the size of the sets in S cannot be larger than k. That is, . The problem is now to pick some subset T' of T such that every set in S contains some element of T', and such that the total weight of all elements in T' is as small as possible.

Property	Value
dbo:abstract	In computer science, k-approximation of k-hitting set is an approximation algorithm for weighted hitting set. The input is a collection S of subsets of some universe T and a mapping W from T to non-negative numbers called the weights of the elements of T. In k-hitting set the size of the sets in S cannot be larger than k. That is, . The problem is now to pick some subset T' of T such that every set in S contains some element of T', and such that the total weight of all elements in T' is as small as possible. (en)
dbo:wikiPageExternalLink	http://algo.inria.fr/seminars/sem00-01/vazirani.html. https://archive.org/details/algorithmdesign0000klei%7Curl-access=registration%7Cyear=2006%7Cisbn=0-321-29535-8
dbo:wikiPageID	14643464 (xsd:integer)
dbo:wikiPageLength	4817 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID	944311179 (xsd:integer)
dbo:wikiPageWikiLink	dbr:Approximation_algorithm dbc:Approximation_algorithms dbr:Computer_science dbr:Linear_programming dbr:Duality_(mathematics) dbr:Collection_(abstract_data_type) dbr:Map_(mathematics) dbr:Set_cover_problem dbr:Subset dbr:Primal-dual_method
dbp:wikiPageUsesTemplate	dbt:Cite_book dbt:Cite_journal
dcterms:subject	dbc:Approximation_algorithms
rdf:type	yago:WikicatApproximationAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932
rdfs:comment	In computer science, k-approximation of k-hitting set is an approximation algorithm for weighted hitting set. The input is a collection S of subsets of some universe T and a mapping W from T to non-negative numbers called the weights of the elements of T. In k-hitting set the size of the sets in S cannot be larger than k. That is, . The problem is now to pick some subset T' of T such that every set in S contains some element of T', and such that the total weight of all elements in T' is as small as possible. (en)
rdfs:label	K-approximation of k-hitting set (en)
owl:sameAs	freebase:K-approximation of k-hitting set yago-res:K-approximation of k-hitting set wikidata:K-approximation of k-hitting set https://global.dbpedia.org/id/4p9JF
prov:wasDerivedFrom	wikipedia-en:K-approximation_of_k-hitting_set?oldid=944311179&ns=0
foaf:isPrimaryTopicOf	wikipedia-en:K-approximation_of_k-hitting_set
is dbo:wikiPageWikiLink of	dbr:Vertex_cover_in_hypergraphs dbr:List_of_numerical_analysis_topics
is foaf:primaryTopic of	wikipedia-en:K-approximation_of_k-hitting_set