0
$\begingroup$

I have an algorithmic problem that requires some lengthy explanation, which follows below.

tl;dr: distribute balls with weights among bags, optimise for balancing both (i) the weights between the bags as well as (ii) the probabilities of picking the balls.

Any help is greatly appreciated.


Formal definition of problem


Let a ball be a type (class) that has

  • a distinct identifier,
  • a set B of z colour(s),
  • a numeric weight (not necessarily distinct), and
  • a boolean unique.

1 ≤ zm (and 1 < m), z and m are integers.

A weight may be negative.


Let a bag (of a colour c) be a tuple of the shape

  • { colour c,
  • set T of balls },

with the restriction that:

  • for each ball, cB.

(The weight of a bag is the sum of the weights of the balls it contains.)


Given

  • positive integers n (such that 2 ≤ nm), p, q,
  • a set S of n colours, and
  • a set R of q balls,

an algorithm f returns

  • n bags, one of each colour in S, containing balls picked only from R (a ball may be picked multiple times),

such that:

  • each bag contains at minimum one ball,
  • unique balls are picked a maximum of once per bag, and
  • the total number of balls (counting all n bags) is equal to p.

Behaviour may be undefined if no solution exists. (In other words, assume that the parameters of f are given to be solvable.)

Optionally, f may also be given a numeric parameter b. See below.


The problem is to find an algorithm f that picks balls to distribute such that it maximises the balance (i. e., minimises the sum of the differences) between

  1. the weights of each bag,

and,

  • if that is balanced within some given bound b for the given R, or in the absence of a known bound,
  • if the maximal possible balance is found and multiple solutions exist at that extremum,

also, for all unique balls in R, between

  1. the probabilities of those balls being picked.

Rationale, simply put: it is desirous to have balanced bags and it is desirous to have balanced probabilities for unique balls to be picked. The former condition takes some priority over the latter.


Winding up…


A trivial brute-force algorithm to satisfy both conditions is to generate all possible distributions, filter for the solutions with maximally balanced bag weights, and randomly pick among them.

Clearly, that has asymptotic growth of both time and space on the order of O(Z̵̢̪͊̎a̵̱̗̱͚̍̂͋̇l̵̘̗̠̗͂g̵̮̼͓̓͋o̷͎͋) and is infeasible for large q.

A probabilistic heuristic algorithm is to repeatedly try randomly distributing balls until a solution is found for which the weight balance is within b. In this case, space complexity is linear, and the algorithm usually finishes within a reasonable length of time (i. e., number of attempts); but it is probabilistic.

This appears to be a variant of the classic knapsack problem, so it's likely to be NP-complete. Might branch-and-bound be a potential strategy? Or possibly a dynamic programming algorithm? (Is the problem sub-recursive?)

The problem of finding a good algorithm has proven challenging for me for some time now, so any input or analysis would be helpful.

Thank you for your time.


Addendum: z has a positive-skewed distribution / has a right long-tailed distribution / is usually < 3.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.