Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/3-partition_problem> ?p ?o }
Showing triples 1 to 34 of
34
with 100 triples per page.
- 3-partition_problem abstract "The 3-partition problem is an NP-complete problem in computer science. The problem is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. More precisely, given a multiset S of n = 3 m positive integers, can S be partitioned into m triplets S1, S2, …, Sm such that the sum of the numbers in each subset is equal? The subsets S1, S2, …, Sm must form a partition of S in the sense that they are disjoint and they cover S. Let B denote the (desired) sum of each subset Si, or equivalently, let the total sum of the numbers in S be m B. The 3-partition problem remains NP-complete when every integer in S is strictly between B/4 and B/2. In this case, each subset Si is forced to consist of exactly three elements (a triple).The 3-partition problem is similar to the partition problem, which in turn is related to the subset sum problem. In the partition problem, the goal is to partition S into two subsets with equal sum. In 3-partition the goal is to partition S into m subsets (or n/3 subsets), not just two subsets, with equal sum.".
- 3-partition_problem wikiPageID "5253859".
- 3-partition_problem wikiPageLength "3135".
- 3-partition_problem wikiPageOutDegree "16".
- 3-partition_problem wikiPageRevisionID "638779648".
- 3-partition_problem wikiPageWikiLink 3-dimensional_matching.
- 3-partition_problem wikiPageWikiLink Category:Strongly_NP-complete_problems.
- 3-partition_problem wikiPageWikiLink Computer_science.
- 3-partition_problem wikiPageWikiLink Cover_(topology).
- 3-partition_problem wikiPageWikiLink David_S._Johnson.
- 3-partition_problem wikiPageWikiLink Disjoint_sets.
- 3-partition_problem wikiPageWikiLink Michael_Garey.
- 3-partition_problem wikiPageWikiLink Multiset.
- 3-partition_problem wikiPageWikiLink NP-completeness.
- 3-partition_problem wikiPageWikiLink Partition_of_a_set.
- 3-partition_problem wikiPageWikiLink Partition_problem.
- 3-partition_problem wikiPageWikiLink Strong_NP-completeness.
- 3-partition_problem wikiPageWikiLink Subset_sum_problem.
- 3-partition_problem wikiPageWikiLink Triplet.
- 3-partition_problem wikiPageWikiLinkText "3-partition problem".
- 3-partition_problem wikiPageWikiLinkText "3-partitioning".
- 3-partition_problem wikiPageUsesTemplate Template:Cite_journal.
- 3-partition_problem subject Category:Strongly_NP-complete_problems.
- 3-partition_problem hypernym Problem.
- 3-partition_problem type Disease.
- 3-partition_problem comment "The 3-partition problem is an NP-complete problem in computer science. The problem is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. More precisely, given a multiset S of n = 3 m positive integers, can S be partitioned into m triplets S1, S2, …, Sm such that the sum of the numbers in each subset is equal? The subsets S1, S2, …, Sm must form a partition of S in the sense that they are disjoint and they cover S.".
- 3-partition_problem label "3-partition problem".
- 3-partition_problem sameAs Q4634256.
- 3-partition_problem sameAs Problema_de_la_3-partición.
- 3-partition_problem sameAs Problema_das_3_Partições.
- 3-partition_problem sameAs m.0db1wd.
- 3-partition_problem sameAs Q4634256.
- 3-partition_problem wasDerivedFrom 3-partition_problem?oldid=638779648.
- 3-partition_problem isPrimaryTopicOf 3-partition_problem.