Matroid-constrained number partitioning (original) (raw)
Matroid-constrained number partitioning is a variant of the multiway number partitioning problem, in which the subsets in the partition should be independent sets of a matroid. The input to this problem is a set S of items, a positive integer m, and some m matroids over the same set S. The goal is to partition S into m subsets, such that each subset i is an independent set in matroid i. Subject to this constraint, some objective function should be minimized, for example, minimizing the largest sum item sizes in a subset. In a more general variant, each of the m matroids has a weight function, which assigns a weight to each element of the ground-set. Various objective functions have been considered. For each of the three operators max,min,sum, one can use this operator on the weights of ite
| Property | Value |
|---|---|
| dbo:abstract | Matroid-constrained number partitioning is a variant of the multiway number partitioning problem, in which the subsets in the partition should be independent sets of a matroid. The input to this problem is a set S of items, a positive integer m, and some m matroids over the same set S. The goal is to partition S into m subsets, such that each subset i is an independent set in matroid i. Subject to this constraint, some objective function should be minimized, for example, minimizing the largest sum item sizes in a subset. In a more general variant, each of the m matroids has a weight function, which assigns a weight to each element of the ground-set. Various objective functions have been considered. For each of the three operators max,min,sum, one can use this operator on the weights of items in each subset, and on the subsets themselves. All in all, there are 9 possible objective functions, each of which can be maximized or minimized. (en) |
| dbo:wikiPageID | 69026625 (xsd:integer) |
| dbo:wikiPageLength | 7349 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1065303066 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Matroid_theory dbr:Free_matroid dbr:Identical-machines_scheduling dbr:Makespan dbr:Spanning_tree dbr:Matroid dbr:Matroid_intersection dbr:Matroid_partitioning dbr:3-partition_problem dbc:Number_partitioning dbr:Balanced_number_partitioning dbr:Graphic_matroid dbr:Greedy_algorithm dbr:Graphical_matroid dbr:Minimum_bottleneck_spanning_tree dbr:Multiway_number_partitioning dbr:Uniform_matroid dbr:Partition_matroid dbr:Unrelated-machines_scheduling |
| dbp:wikiPageUsesTemplate | dbt:Clarify dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Matroid_theory dbc:Number_partitioning |
| rdfs:comment | Matroid-constrained number partitioning is a variant of the multiway number partitioning problem, in which the subsets in the partition should be independent sets of a matroid. The input to this problem is a set S of items, a positive integer m, and some m matroids over the same set S. The goal is to partition S into m subsets, such that each subset i is an independent set in matroid i. Subject to this constraint, some objective function should be minimized, for example, minimizing the largest sum item sizes in a subset. In a more general variant, each of the m matroids has a weight function, which assigns a weight to each element of the ground-set. Various objective functions have been considered. For each of the three operators max,min,sum, one can use this operator on the weights of ite (en) |
| rdfs:label | Matroid-constrained number partitioning (en) |
| owl:sameAs | wikidata:Matroid-constrained number partitioning https://global.dbpedia.org/id/G7CQC |
| prov:wasDerivedFrom | wikipedia-en:Matroid-constrained_number_partitioning?oldid=1065303066&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Matroid-constrained_number_partitioning |
| is dbo:wikiPageWikiLink of | dbr:Matroid_partitioning dbr:Balanced_number_partitioning |
| is foaf:primaryTopic of | wikipedia-en:Matroid-constrained_number_partitioning |