dbo:abstract
|
- The multiple subset sum problem is an optimization problem in computer science and operations research. It is a generalization of the subset sum problem. The input to the problem is a multiset of n integers and a positive integer m representing the number of subsets. The goal is to construct, from the input integers, some m subsets. The problem has several variants:
* Max-sum MSSP: for each subset j in 1,...,m, there is a capacity Cj. The goal is to make the sum of all subsets as large as possible, such that the sum in each subset j is at most Cj.
* Max-min MSSP (also called bottleneck MSSP or BMSSP): again each subset has a capacity, but now the goal is to make the smallest subset sum as large as possible.
* Fair SSP: the subsets have no fixed capacities, but each subset belongs to a different person. The utility of each person is the sum of items in his/her subsets. The goal is to construct subsets that satisfy a given criterion of fairness, such as max-min item allocation. (en)
|
dbo:wikiPageID
| |
dbo:wikiPageLength
|
- 10139 (xsd:nonNegativeInteger)
|
dbo:wikiPageRevisionID
| |
dbo:wikiPageWikiLink
| |
dbp:wikiPageUsesTemplate
| |
dcterms:subject
| |
rdfs:comment
|
- The multiple subset sum problem is an optimization problem in computer science and operations research. It is a generalization of the subset sum problem. The input to the problem is a multiset of n integers and a positive integer m representing the number of subsets. The goal is to construct, from the input integers, some m subsets. The problem has several variants: (en)
|
rdfs:label
| |
owl:sameAs
| |
prov:wasDerivedFrom
| |
foaf:isPrimaryTopicOf
| |
is dbo:wikiPageRedirects
of | |
is dbo:wikiPageWikiLink
of | |
is foaf:primaryTopic
of | |