Matches in DBpedia 2016-04 for { <http://wikidata.dbpedia.org/resource/Q4634256> ?p ?o }
Showing triples 1 to 18 of
18
with 100 triples per page.
- Q4634256 subject Q8819585.
- Q4634256 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.".
- Q4634256 wikiPageWikiLink Q1065968.
- Q4634256 wikiPageWikiLink Q10866593.
- Q4634256 wikiPageWikiLink Q1154420.
- Q4634256 wikiPageWikiLink Q159225.
- Q4634256 wikiPageWikiLink Q21198.
- Q4634256 wikiPageWikiLink Q215206.
- Q4634256 wikiPageWikiLink Q215382.
- Q4634256 wikiPageWikiLink Q331481.
- Q4634256 wikiPageWikiLink Q381060.
- Q4634256 wikiPageWikiLink Q6830528.
- Q4634256 wikiPageWikiLink Q7624684.
- Q4634256 wikiPageWikiLink Q864377.
- Q4634256 wikiPageWikiLink Q8819585.
- Q4634256 wikiPageWikiLink Q92801.
- Q4634256 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.".
- Q4634256 label "3-partition problem".