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$
3
  • $\begingroup$ Why do you expect such an algorithm to exist? $\endgroup$ Nov 14, 2015 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$ Nov 16, 2015 at 8:22
  • $\begingroup$ A couple approaches in Sage have shown up on Math.SE. $\endgroup$ Jun 7, 2016 at 20:22

1 Answer 1

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$
5
  • $\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$ Nov 16, 2015 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$ Nov 16, 2015 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$ Nov 16, 2015 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$ Nov 16, 2015 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$ Nov 16, 2015 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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