All Questions
8
questions
1
vote
1
answer
149
views
How to assign tasks to a set of machines, given that the more tasks you assign to a machine the slower they will run? Bin covering with merging bins?
Intro
I need to design an algorithm that will distribute a known set of tasks with a known RAM requirement to a known set of machines with known RAM capacities. The tasks require a certain amount of ...
- 113
1
vote
0
answers
59
views
How to calculate the number of set partitions of an arbitrary set? [duplicate]
Pre-Amble
I would like to rephrase the question
PREVIOUS INSTANCE OF THIS QUESTION ( Was closed due to an alleged duplicity ).
Considering sets of four elements we can consider sets of the following ...
- 2,789
0
votes
0
answers
49
views
Conditions for a sorted partition of the edges of $K_n$ to generate a total order of the vertices
Given a complete undirected graph $K_n$, it's given a refinement algorithm that builds, at iteration $t$, a sorted partition $E^t$ of the edges and a sorted partition $V^t$ of the vertices by refining ...
- 451
3
votes
2
answers
754
views
How to calculate the number of possible multiset partitions into N disjoint sets?
I have made a Ruby program, which enumerates the possible multiset partitions, into a given number of disjoint sets (N), also called bins. The bins are indistinguishable. They can be sorted in any ...
- 155
1
vote
1
answer
181
views
Restricted Growth Function and Partition
Can someone explain how do I convert from Partition to Restricted Growth Function to and vice versa? For example: how [1,1,1,2] is the RGF of {{1,2,3},{4}} partition?
I have read the definitions but ...
- 31
3
votes
1
answer
309
views
Algorithm to partition a multiset into $K$ equal sized multisets
How can I partition a multiset of integers, $A$, of size $N=MK$, into $K$ equal-sized multisets, $G_1,G_2,\ldots,G_K$, such that $\sum_i \mathrm{\lvert \min(G_i)\rvert}$ is maximized? Here, $\min(G)$ ...
- 53
0
votes
3
answers
1k
views
For a set with N members, what is the number of set partitions in which each subset is either of size 1 or 2? [duplicate]
I have a set with $N$ members $\{1,2, \dots, N\}$. I would like to know number of set partitions in which each subset is either of size $1$ or $2$, i.e., cardinality of each subset in the partition is ...
- 327
2
votes
1
answer
3k
views
Divide a set of $n$ elements into $k$ subsets having equal sum
Is there / Can there be an algorithm with acceptable time complexity that solves the following?
Given $n \leq 20$ non-negative numbers, determine whether the $n$ numbers can be divided into $k \leq ...
