# Tag Info

Accepted

### Sample a set of N numbers without replacement, each element taken from N different weighted sets

There is a mapping from each possible list $P$ to an interval $[\ell,r)$ contained in $[0,1)$, such that the resulting intervals (if you consider all possible lists) form a partition of $[0,1)$. In ...
• 141k
1 vote
Accepted

### A lower bound for the makespan of heterogenous fog nodes

Under the assumption that $EXT(N_i) = \mathit{MinMakespan}$, $$\sum_{k \in N_i \mathit{Tasks}} \mathit{length}(T_k) = \mathit{MinMakespan} \times \mathit{CPUrate}(N_i).$$ Therefore  \sum_k \mathit{...
• 270k
Accepted

### Boolean Logic for Floats

I recommend that you look up 'Fuzzy Logic'.
• 46

### N Queens Problem - Number of Possible Placements

About the "computationally expensive": They calculated the number of ways to put eight queens onto 8 fields of an 8x8 chessboard, ignoring the identity of the queens. But anybody in their ...
• 25.2k
1 vote

### Alternate proof of the Caro-Wei theorem for lower bounding the independence number

Induction on the order of G . True for |G| = 1. Assume for |G| = n let prove it for |G| = n +1. Choose a vertex v of minimum degree . Consider H = G - N[v]. Clearly a(G)> = 1 + a(H) > = 1 + sum {...
1 vote

### Alternate proof of the Caro-Wei theorem for lower bounding the independence number

There are several non-probabilisitc proofs : 1/ using greedy algorithm deleting minimum degree : See : https://www.sciencedirect.com/science/article/pii/S0166218X13001339 https://onlinelibrary.wiley....
Accepted

### N Queens Problem - Number of Possible Placements

4,426,165,368 is the number of ways to place 8 identical queens into 64 places, i.e the number of combinations. "Identical" means positions are considered equivalent if one queen is swapped ...
• 826

### Given a permutation of n integers, how fast can a corresponding Standard Young's Tableau be created?

I believe that no faster algorithm is known, at least if you are interested in computing both tableaux. Dan Romik shows in his paper The Number of Steps in the Robinson-Schensted Algorithm that on ...
• 270k
This is called Enumerative Coding and was introduced by Tom Cover. Consider a word $W$ that is $n$ bits long, where the one bits are in locations $x_k, \ldots, x_1$ with \$x_k>x_{k-1}>\cdots>...