New answers tagged

0 votes
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 ...
user avatar
  • 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{...
user avatar
3 votes
Accepted

Boolean Logic for Floats

I recommend that you look up 'Fuzzy Logic'.
user avatar
  • 46
0 votes

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 ...
user avatar
  • 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 {...
user avatar
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....
user avatar
2 votes
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 ...
user avatar
  • 826
2 votes

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 ...
user avatar
3 votes
Accepted

Generating the n-th number with k bits set, is it possible?

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>...
user avatar
  • 459

Top 50 recent answers are included