Expand description
Set-based problems.
This module contains NP-hard problems based on set operations:
ConsecutiveSets: Consecutive arrangement of subset elements in a stringExactCoverBy3Sets: Exact cover by 3-element subsets (X3C)ComparativeContainment: Compare containment-weight sums for two set familiesIntegerKnapsack: Maximize value with integer multiplicities subject to capacityMaximumSetPacking: Maximum weight set packingMinimumHittingSet: Minimum-size universe subset hitting every setMinimumSetCovering: Minimum weight set coverPrimeAttributeName: Determine if an attribute belongs to any candidate keyRootedTreeStorageAssignment: Extend subsets to directed tree paths within a total-cost boundSetBasis: Minimum-cardinality basis generating all sets by unionSetSplitting: 2-color universe so every specified subset is non-monochromaticThreeDimensionalMatching: Perfect matching in a tripartite 3-uniform hypergraphThreeMatroidIntersection: Common independent set of size K in three partition matroidsTwoDimensionalConsecutiveSets: 2D consecutive arrangement of subset elementsMinimumCardinalityKey: Smallest attribute set that uniquely identifies tuples
Structsยง
- Comparative
Containment - Comparative Containment.
- Consecutive
Sets - Consecutive Sets problem.
- Exact
Cover By3Sets - Exact Cover by 3-Sets (X3C) problem.
- Integer
Knapsack - The Integer Knapsack problem.
- Maximum
SetPacking - The Set Packing problem.
- Minimum
Cardinality Key - The Minimum Cardinality Key optimization problem.
- Minimum
Hitting Set - The Minimum Hitting Set problem.
- Minimum
SetCovering - The Set Covering problem.
- Prime
Attribute Name - Prime Attribute Name decision problem.
- Rooted
Tree Storage Assignment - SetBasis
- The Set Basis decision problem.
- SetSplitting
- The Set Splitting problem.
- Three
Dimensional Matching - Three-Dimensional Matching (3DM) problem.
- Three
Matroid Intersection - Three-Matroid Intersection problem.
- TwoDimensional
Consecutive Sets - 2-Dimensional Consecutive Sets problem.