Expand description
Miscellaneous problems.
Problems with unique input structures that don’t fit other categories:
AdditionalKey: Determine whether a relational schema has an additional candidate keyBetweenness: Find a linear ordering satisfying betweenness constraints on triplesBinPacking: Bin Packing (minimize bins)Clustering: Partition elements into bounded-diameter clustersCyclicOrdering: Find a permutation satisfying cyclic ordering constraints on triplesBoyceCoddNormalFormViolation: Boyce-Codd Normal Form Violation (BCNF)ConsistencyOfDatabaseFrequencyTables: Pairwise frequency-table consistencyConjunctiveBooleanQuery: Evaluate a conjunctive Boolean query over relationsConjunctiveQueryFoldability: Conjunctive Query FoldabilityDynamicStorageAllocation: Assign starting addresses in bounded memory for time-varying itemsExpectedRetrievalCost: Allocate records to circular sectors within a latency boundFactoring: Integer factorizationFeasibleRegisterAssignment: Determine if a DAG computation can be scheduled without register conflicts under a fixed assignmentIntegerExpressionMembership: Membership in a set defined by an integer expression treeFlowShopScheduling: Flow Shop Scheduling (meet deadline on m processors)GroupingBySwapping: Group equal symbols into contiguous blocks by adjacent swapsJobShopScheduling: Minimize makespan with per-job processor routesKnapsack: 0-1 Knapsack (maximize value subject to weight capacity)MultiprocessorScheduling: Schedule tasks on processors to meet a deadlineNumerical3DimensionalMatching: Partition W∪X∪Y into m triples each summing to BNumericalMatchingWithTargetSums: Partition X∪Y into m pairs with pair sums matching targetsOpenShopScheduling: Open Shop Scheduling (minimize makespan, free task order per job)LongestCommonSubsequence: Longest Common SubsequenceMaximumLikelihoodRanking: Find a ranking minimizing total pairwise disagreementMinimumAxiomSet: Find smallest axiom subset whose deductive closure covers all true sentencesMinimumCodeGenerationOneRegister: Minimize instruction count for a one-register machineMinimumCodeGenerationParallelAssignments: Minimize backward dependencies when ordering parallel assignmentsMinimumCodeGenerationUnlimitedRegisters: Minimize instruction count for an unlimited-register machine with 2-address instructionsMinimumExternalMacroDataCompression: Minimize compression cost using external dictionaryMinimumFaultDetectionTestSet: Find minimum set of input-output paths covering all internal DAG verticesMinimumInternalMacroDataCompression: Minimize self-referencing compression costMinimumRegisterSufficiencyForLoops: Minimize registers for loop variable allocation (circular arc coloring)MinimumWeightAndOrGraph: Find minimum-weight solution subgraph in a DAG with AND/OR gatesMinimumTardinessSequencing: Minimize tardy tasks in single-machine schedulingOptimumCommunicationSpanningTree: Find spanning tree minimizing total weighted communication costPaintShop: Minimize color switches in paint shop schedulingCosineProductIntegration: Balanced sign assignment for integer frequenciesNonLivenessFreePetriNet: Determine whether a free-choice Petri net is not livePartition: Partition a multiset into two equal-sum subsetsPartiallyOrderedKnapsack: Knapsack with precedence constraintsPrecedenceConstrainedScheduling: Schedule unit tasks on processors by deadlinePreemptiveScheduling: Preemptive parallel scheduling with precedences (minimize makespan)ProductionPlanning: Meet all period demands within capacity and total-cost boundsRectilinearPictureCompression: Cover 1-entries with bounded rectanglesRegisterSufficiency: Evaluate DAG computation with bounded registersResourceConstrainedScheduling: Schedule unit-length tasks on processors with resource constraintsSchedulingWithIndividualDeadlines: Meet per-task deadlines on parallel processorsStackerCrane: Minimize the total length of a closed walk through required arcsSequencingToMinimizeMaximumCumulativeCost: Keep every cumulative schedule cost prefix under a boundSequencingToMinimizeTardyTaskWeight: Minimize total weight of tardy tasksSequencingToMinimizeWeightedCompletionTime: Minimize total weighted completion timeSequencingToMinimizeWeightedTardiness: Decide whether a schedule meets a weighted tardiness boundSequencingWithDeadlinesAndSetUpTimes: Single-machine scheduling feasibility with compiler-switch setup penaltiesSequencingWithReleaseTimesAndDeadlines: Single-machine scheduling feasibilitySequencingWithinIntervals: Schedule tasks within time windowsShortestCommonSupersequence: Find a common supersequence of bounded lengthSquareTiling: Place colored square tiles on an N x N grid with matching edge colorsTimetableDesign: Schedule craftsmen on tasks across work periodsStringToStringCorrection: String-to-String Correction (derive target via deletions and swaps)SubsetProduct: Find a subset whose product equals exactly a target valueSubsetSum: Find a subset summing to exactly a target valueSumOfSquaresPartition: Partition integers into K groups minimizing sum of squared group sums
Structs§
- Additional
Key - The Additional Key problem.
- Betweenness
- BinPacking
- The Bin Packing problem.
- Boyce
Codd Normal Form Violation - The Boyce-Codd Normal Form Violation decision problem.
- Capacity
Assignment - Capacity Assignment optimization problem.
- CbqRelation
- A relation with fixed arity and a set of tuples over a finite domain.
- Clustering
- The Clustering problem.
- Conjunctive
Boolean Query - The Conjunctive Boolean Query problem.
- Conjunctive
Query Foldability - The Conjunctive Query Foldability problem.
- Consistency
OfDatabase Frequency Tables - The Consistency of Database Frequency Tables decision problem.
- Cosine
Product Integration - The Cosine Product Integration problem.
- Cyclic
Ordering - Dynamic
Storage Allocation - Dynamic Storage Allocation problem.
- Ensemble
Computation - Expected
Retrieval Cost - Factoring
- The Integer Factoring problem.
- Feasible
Register Assignment - The Feasible Register Assignment problem.
- Flow
Shop Scheduling - The Flow Shop Scheduling problem.
- Frequency
Table - Grouping
BySwapping - Grouping by Swapping.
- Integer
Expression Membership - The Integer Expression Membership problem.
- JobShop
Scheduling - Knapsack
- The 0-1 Knapsack problem.
- Known
Value - KthLargestM
Tuple - The Kth Largest m-Tuple problem.
- Longest
Common Subsequence - The Longest Common Subsequence problem.
- Maximum
Likelihood Ranking - The Maximum Likelihood Ranking problem.
- Minimum
Axiom Set - The Minimum Axiom Set problem.
- Minimum
Code Generation OneRegister - Minimum Code Generation on a One-Register Machine.
- Minimum
Code Generation Parallel Assignments - The Minimum Code Generation for Parallel Assignments problem.
- Minimum
Code Generation Unlimited Registers - Minimum Code Generation with Unlimited Registers.
- Minimum
Decision Tree - Minimum Decision Tree problem.
- Minimum
Disjunctive Normal Form - Minimum Disjunctive Normal Form problem.
- Minimum
External Macro Data Compression - Minimum External Macro Data Compression problem.
- Minimum
Fault Detection Test Set - The Minimum Fault Detection Test Set problem.
- Minimum
Internal Macro Data Compression - Minimum Internal Macro Data Compression problem.
- Minimum
Register Sufficiency ForLoops - The Minimum Register Sufficiency for Loops problem.
- Minimum
Tardiness Sequencing - Minimum Tardiness Sequencing problem.
- Minimum
Weight AndOr Graph - The Minimum Weight AND/OR Graph problem.
- Multiprocessor
Scheduling - The Multiprocessor Scheduling problem.
- NonLiveness
Free Petri Net - Numerical3
Dimensional Matching - Numerical
Matching With Target Sums - Open
Shop Scheduling - The Open Shop Scheduling problem.
- Optimum
Communication Spanning Tree - The Optimum Communication Spanning Tree problem.
- Paint
Shop - The Paint Shop problem.
- Partially
Ordered Knapsack - Partition
- The Partition problem.
- Precedence
Constrained Scheduling - The Precedence Constrained Scheduling problem.
- Preemptive
Scheduling - The Preemptive Scheduling problem.
- Production
Planning - Rectilinear
Picture Compression - The Rectilinear Picture Compression problem.
- Register
Sufficiency - The Register Sufficiency problem.
- Resource
Constrained Scheduling - The Resource Constrained Scheduling problem.
- Scheduling
ToMinimize Weighted Completion Time - Scheduling to Minimize Weighted Completion Time problem.
- Scheduling
With Individual Deadlines - Scheduling With Individual Deadlines.
- Sequencing
ToMinimize Maximum Cumulative Cost - Sequencing to Minimize Maximum Cumulative Cost.
- Sequencing
ToMinimize Tardy Task Weight - Sequencing to Minimize Tardy Task Weight problem.
- Sequencing
ToMinimize Weighted Completion Time - Sequencing to Minimize Weighted Completion Time problem.
- Sequencing
ToMinimize Weighted Tardiness - Sequencing to Minimize Weighted Tardiness.
- Sequencing
With Deadlines AndSet UpTimes - Sequencing with Deadlines and Set-Up Times problem.
- Sequencing
With Release Times AndDeadlines - Sequencing with Release Times and Deadlines.
- Sequencing
Within Intervals - Sequencing Within Intervals problem.
- Shortest
Common Supersequence - The Shortest Common Supersequence problem.
- Square
Tiling - Stacker
Crane - The Stacker Crane problem.
- Staff
Scheduling - The Staff Scheduling problem.
- String
ToString Correction - The String-to-String Correction problem.
- Subset
Product - The Subset Product problem.
- Subset
Sum - The Subset Sum problem.
- SumOf
Squares Partition - The Sum of Squares Partition problem (Garey & Johnson SP19).
- Three
Partition - Timetable
Design - The Timetable Design problem.