Matches in DBpedia 2014 for { <http://dbpedia.org/resource/3-partition_problem> ?p ?o. }
Showing items 1 to 14 of
14
with 100 items 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 subsets 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 three subsets, with equal sum.".
- 3-partition_problem wikiPageID "5253859".
- 3-partition_problem wikiPageRevisionID "544388670".
- 3-partition_problem hasPhotoCollection 3-partition_problem.
- 3-partition_problem subject Category:Strongly_NP-complete_problems.
- 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 subsets 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 label "Problema de la 3-partición".
- 3-partition_problem sameAs Problema_de_la_3-partición.
- 3-partition_problem sameAs m.0db1wd.
- 3-partition_problem sameAs Q4634256.
- 3-partition_problem sameAs Q4634256.
- 3-partition_problem wasDerivedFrom 3-partition_problem?oldid=544388670.
- 3-partition_problem isPrimaryTopicOf 3-partition_problem.