5
$\begingroup$

The refinement order on partitions of an integer $n$ can be defined as follows: $\lambda=(\lambda_1,\dots,\lambda_k)\leq\mu=(\mu_1,\dots,\mu_\ell)$ if there is a partition of the parts of $\lambda$ into blocks whose sums are the parts of $\mu$.

It is known that the problem of deciding whether $\lambda\leq\mu$ is NP-complete. However, for a practical application I would need an algorithm which performs reasonably when $n$ is around $200$. Ideally, this algorithm would already have a (free) implementation...

I tried the following naive approach:

  • find the last index $j$ such that $\mu_j>\lambda_1$
  • if $\mu_{j+1} = \lambda_1$ remove $\mu_{j+1}$ from $\mu$ and $\lambda_1$ from $\lambda$ and recurse
  • otherwise, for $j\in\{j,j-1,\dots,1\}$:
    • subtract $\lambda_1$ from $\mu_j$ and reorder to obtain a new partition, and recurse with this partition and the rest of $\lambda$

Although this seems to work reasonably well for many pairs $(\lambda,\mu)$ of partitions of size around $200$, it performs poorly when $\lambda$ has many small parts but is not a refinement of $\mu$.

$\endgroup$
  • $\begingroup$ Why do you expect such an algorithm to exist? $\endgroup$ – Yuval Filmus Nov 14 '15 at 14:40
  • $\begingroup$ @YuvalFilmus: I am only hoping for it, because I would like to use it. Perhaps I do have some hope because even the simple approach I outlined above seems to perform very badly only in very few cases. I'd also be interested in any experiments other people did. $\endgroup$ – Martin Rubey Nov 16 '15 at 8:22
  • $\begingroup$ A couple approaches in Sage have shown up on Math.SE. $\endgroup$ – Austin Mohr Jun 7 '16 at 20:22
3
$\begingroup$

I suggest you try using integer linear programming. Introduce $k\ell$ zero-or-one variables $x_{i,j}$, with the constraints

$$\sum_j x_{i,j} \lambda_j = \mu_i$$

and

$$\sum_i x_{i,j} = 1.$$

Feed it to an off-the-shelf ILP solver. If it can find a feasible solution for you, then you know that $\lambda \le \mu$. If it can determine that no solution exists, then you know that $\lambda \not\le \mu$.

$\endgroup$
  • $\begingroup$ Admittedly a very "soft" question: should I expect that a specialised approach (whatever that would be) performs in the worst case just as badly as this approach? $\endgroup$ – Martin Rubey Nov 16 '15 at 7:55
  • 1
    $\begingroup$ I did a test, indeed it seems that linear programming (I used cplex) is better in the worst case. I ran (a slightly refined) version of the algorithm in the question for 1000 random partitions of 100, and got a worst case timing of 320 seconds, whereas MILP's worst case was around 0.1 seconds. $\endgroup$ – Martin Rubey Nov 16 '15 at 9:39
  • $\begingroup$ My comment above has bad numbers, but seems to be essentially correct. (I found a partition of 200 where "my" algorithm takes around 20 seconds, but nothing like that for cplex.) Sorry for the noise. $\endgroup$ – Martin Rubey Nov 16 '15 at 9:54
  • $\begingroup$ Unfortunately, it seems that only cplex does the job quickly. I tried GLPK and CBC now, and they are both unusable for the problem, it appears... $\endgroup$ – Martin Rubey Nov 16 '15 at 11:52
  • $\begingroup$ Sorry, with "linear programming" I meant "integer linear programming". The "only" remaining problem is that I probably can't use cplex for the real thing (a website), and GLPK and CBC are not up to the task... $\endgroup$ – Martin Rubey Nov 16 '15 at 16:27

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.