Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Set_packing> ?p ?o. }
Showing items 1 to 32 of
32
with 100 items per page.
- Set_packing abstract "Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems.Suppose we have a finite set S and a list of subsets of S. Then, the set packing problem asks if some k subsets in the list are pairwise disjoint (in other words, no two of them share an element).More formally, given a universe and a family of subsets of ,a packing is a subfamily of sets such that all sets in are pairwise disjoint, and the size of the packing is . In the set packing decision problem, the input is a pair and an integer the question is whetherthere is a set packing of size or more. In the set packing optimization problem, the input is a pair , and the task is to find a set packing that uses the most sets. The problem is clearly in NP since, given k subsets, we can easily verify that they are pairwise disjoint in polynomial time.The optimization version of the problem, maximum set packing, asks for the maximum number of pairwise disjoint sets in the list. It is a maximization problem that can be formulated naturally as an integer linear program, belongs to the class of packing problems, and its dual linear program is the set cover problem.".
- Set_packing wikiPageExternalLink implement.shtml.
- Set_packing wikiPageExternalLink wwwcompendium.
- Set_packing wikiPageExternalLink node144.html.
- Set_packing wikiPageExternalLink setpacking.html.
- Set_packing wikiPageExternalLink set-benchmarks.htm.
- Set_packing wikiPageExternalLink solving-packaging-problem-in-php.html.
- Set_packing wikiPageExternalLink NODE202.HTM.
- Set_packing wikiPageID "2017636".
- Set_packing wikiPageRevisionID "602667845".
- Set_packing hasPhotoCollection Set_packing.
- Set_packing subject Category:Combinatorics.
- Set_packing subject Category:NP-complete_problems.
- Set_packing type Abstraction100002137.
- Set_packing type Attribute100024264.
- Set_packing type Condition113920835.
- Set_packing type Difficulty114408086.
- Set_packing type NP-completeProblems.
- Set_packing type Problem114410605.
- Set_packing type State100024720.
- Set_packing comment "Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems.Suppose we have a finite set S and a list of subsets of S.".
- Set_packing label "Mengenpackungsproblem".
- Set_packing label "Set packing".
- Set_packing label "Set packing".
- Set_packing sameAs Mengenpackungsproblem.
- Set_packing sameAs Set_packing.
- Set_packing sameAs m.06fdth.
- Set_packing sameAs Q475603.
- Set_packing sameAs Q475603.
- Set_packing sameAs Set_packing.
- Set_packing wasDerivedFrom Set_packing?oldid=602667845.
- Set_packing isPrimaryTopicOf Set_packing.