The partitions tag has no wiki summary.
5
votes
1answer
68 views
What is a compact way to represent a partition of a set?
There exist efficient data
structures for representing set
partitions. These data structures have good time complexities for operations
like Union and Find, but they are not particularly ...
2
votes
1answer
190 views
reducing subset-sum to partition
Subset-sum: Given a list of numbers, find if a non-empty sublist has sum 0 (there's a variation where we want sum=k instead of 0, but 0 is easier for analysis)
Partition: Given a list, can it ...
6
votes
0answers
76 views
How to distribute items of varying sizes into bins of varying sizes, such that percent utilization across all bins is minimized?
I have a bunch of databases, each having different access patterns, such that each puts a different amount of load on its database cluster. I would like to distribute them around my set of database ...
1
vote
1answer
145 views
Showing a partition-like problem is NP-complete
Given a set $A=\{a_{1},a_{2},a_{3},\ldots,a_{n}\}$, then construct a set $P=\{p_{1}, p_{2}, p_{3}, \ldots , p_{n}\}$ such that
$|p_{i}|=a_{i}$, and
$\sum_{i = 1,}^{n}p_{i} = 0$.
This problem is ...
7
votes
0answers
120 views
Problems for which algorithms based on partition refinement run faster than in loglinear time
Partition refinement is a technique in which you start with a finite set of objects and progressively split the set. Some problems, like DFA minimization, can be solved using partition refinement ...
4
votes
1answer
93 views
Data structure for partition of a set
A partition of a set S is a separation of the set into an arbitrary number of non-empty, pairwise disjoint subsets whose union is exactly S. What manner of a data structure should be used to represent ...
