Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let say we have the following set $S = \{x_1, x_2, x_3, ..., x_n\}$ where $x_i$ is a real number between $0$ and $1$.

Now I want to find an algorithm that randomly generates a subset of $S$, free to for each $x$ choose an arbitrary real number between $0$ and $1$, with the following constraint:
$x_1 + x_2 + ... + x_n = B$, where $B$ being a budget of some sort.

Examples of a subset would be (given $B = 2$ and $n = 10$) are:
$\{x_1 = 0.6, x_2 = 0.4, x_{3} = 1\}$, $\{x_1 = 0.2, x_2 = 0.8, x_{3} = 0.5, x_{7} = 0.5\}$, etc.

Now lets look at a more complex version. Say I don't like that $\{1, 1\}$ has the same "cost" as $\{0.5, 0.5, 0.5, 0.5\}$. Instead I want the cost to be exponential, making it very expensive to choose values closer to $1$. In addition I want to add a constant cost to make it more cost-effective to focus on a few stronger values, preventing results like $\{0.00000001, 0.00000001, ..., 0.0000001\}$. The above constraint would then instead be:
$f(x) = C \ \operatorname{sgn}(x) + ke^{ax}$,
where $C, a, k$ are constants, and $$f(x_1) + f(x_2) + f(x_3) + ... + f(x_n) = B ,$$

where $f(x)$ is a cost function of sorts.

To clarify, I'm not necessarily looking for subsets that exactly add up to $B$, instead I'm looking for something that is somehow bounded by $B$, making different subsets generated by the same algorithm to be comparable to each other in a "fair" sort of way.

Now I posted this here at stackoverflow where I got the advice to try here instead. I realize now though that I probably didn't explain it very well over there.

share|improve this question
2  
I think the problem is still underspecified. How do you know that there is any subset of $S$ that sums to $B$? How do you know that there is more than one? Do you really require that the sum is no more than $B$? –  Craig Sep 15 '11 at 23:25
    
Well I don't really want it to sum exactly B, but at least no more than B. What I want is to be able to generate subsets of S through some randomized process while upholding some sort of "fairness" between the results. –  moevi Sep 15 '11 at 23:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.