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 S to non-negative numbers called the weights of the elements of S. In k-hitting set the size of the sets in S cannot be larger than k. That is, <math>\forall i \in S: |i| \leq k</math>.
| Property | Value |
|---|
| dbpprop: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 S to non-negative numbers called the weights of the elements of S. In k-hitting set the size of the sets in S cannot be larger than k. That is, <math>\forall i \in S: |i| \leq k</math>. 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.
|
| rdf:type
| |
| 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 S to non-negative numbers called the weights of the elements of S. In k-hitting set the size of the sets in S cannot be larger than k. That is, <math>\forall i \in S: |i| \leq k</math>.
|
| rdfs:label
|
- K-approximation of k-hitting set
|
| owl:sameAs
| |
| skos:subject
| |
| foaf:page
| |
| is owl:sameAs
of | |
![[RDF Data]](/statics/sw-cube.png)
