4
$\begingroup$

I need to divide 48 pieces of jewelry between 3 inheritors so as to give equal, or nearly equal value, to each. I have learned that this is called the 3-partition problem. I solved it for 9 pieces of jewely by exhaustive enumeration (some 19,000 possibilities) in a spreadsheet (LibreOffice Calc). No big deal. But all 48 pieces becomes a big deal.

I don't actually need a perfect solution. A heuristic algorithm would suffice if it were acknowledged as an acceptable solution scheme by some set of professionals; programmers, estate settling lawyers, etc. In other words using a technique recognized as "good enough" will be good enough for my purpose.

This question is also posted on StackOverflow. They suggested I post here.

Thank you, David

Improve this question
$\endgroup$
10
  • $\begingroup$ The problem is NP-complete to find an exact 3-partition; see the short Wikipedia description: en.wikipedia.org/wiki/3-partition_problem. So you have two choices: An exhaustive search of all possibilities, or approximation algorithms. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 1, 2011 at 1:58
  • $\begingroup$ To: Joseph O'Rourke: it is the approximation algorithms that I seek. Where is one described? I've been on mathisfun and codingthewheel and don't find it there. $\endgroup$
    – Grabs At Strawberries
    Commented Dec 1, 2011 at 3:54
  • $\begingroup$ The first thing I'd do is to take a brief look at how the appraised values are distributed. You may find that it is obviously problematic (for example, if there are just a handful of exceptionally valuable pieces, which can't themselves be divided evenly into thirds, and the remaining pieces can't make up the difference). If you are lucky, there will be many pieces with roughly comparable values. In that case, simple randomized heuristics probably get you close enough for practical purposes (since, unless you actually have an offer on the table, the appraisals will have some error anyway). $\endgroup$
    – Henry Cohn
    Commented Dec 1, 2011 at 4:34
  • $\begingroup$ One difficulty in giving an abstract answer is that it's not clear how to model this. For example, one could try to bound the worst-case approximation ratio; this is an interesting theoretical question, but I'm not convinced it would shed much light on what you can do in practice. It really depends on the numbers. $\endgroup$
    – Henry Cohn
    Commented Dec 1, 2011 at 4:40
  • 1
    $\begingroup$ I suggest you hire a mathematical consultant. Mathematicians have put in the hard yards to get to where they can solve this kind of problem; they deserve to be paid for their specialist skills. $\endgroup$
    – Gerry Myerson
    Commented Dec 1, 2011 at 5:03

2 Answers 2

Reset to default
4
$\begingroup$

There exists a pseudo-polynomial time dynamic programming solution to this problem, for which running time and storage complexity depend on the sum of costs of the pieces of jewelry, denoted $S$. If the sum of costs, $S$, is small then the algorithm would be practical as its storage is $O(S^2)$ and its running time is $O(S^2N)$, $N$ being the number of pieces (48 here).

To get a sense of the algorithm take a look at the Subset sum problem Wikipedia page--dynamic programming solution. This concerns finding a subset of items which sums to a particular cost. Clearly you can solve the 2-partition problem by using the subset sum solutions, i.e., by enumerating over all the potential subset sums, and choosing the one that you prefer for any reason.

Now generalizing to 3-partition is straightforward. You basically solve the double-subset sum problem. You store $Q(i,s, t)$ to be the value (true or false) of "whether there are two disjoint subsets of $x_1, \ldots, x_i$ which respectively sum to $s$ and $t$". You can easily update $Q(i, s, t)$ by adding new items. Again one can enumerate over the potential $Q(N, s, t)$'s and choose the one that is considered best.

Obviously even if $S$ is large, the costs can be quantized using larger cost units, which results in a measurable upper bound on the error. This also can be used combined with the solution of Brendan McKay to guide a local search algorithm.

Improve this answer
$\endgroup$
1
  • $\begingroup$ As a (perhaps useless) supplement to this description, Exercise 6.25 in the Dynamic Programming chapter of Vazirani's algorithms textbook (PDF: cs.berkeley.edu/~vazirani/algorithms/chap6.pdf) asks to devise "a dynamic programming algorithm for 3- PARTITION that runs in time polynomial in $n$ and in" $S$. [p.197] $\endgroup$
    – Joseph O'Rourke
    Commented Dec 1, 2011 at 20:50
2
$\begingroup$

To get a good approximation, I suggest a local refinement algorithm. Define some success measure (like the maximum value of a share minus the minimum value). Start with any distribution into three shares.

Now move a small number of pieces into different shares if they improve the success measure. Keep doing that until no such improvement is possible. With 48 items, you should be able to find a partition where no movement of 4 or fewer items improves the success measure, and this will be a fairly good solution.

Start with different random partitions to see if you get the same final result. If so, there is a fair chance (in practice, not in theory!) that you have the best solution. If you get multiple final results, you can at least choose the best one.

A variation is to allow movement of a small number of pieces with low probability even if the success gets worse. Maybe the probability can depend on how much worse the success gets. This can get you out of local minima but you will never find the global minimum if you set the probabilities too high.

More sophisticated algorithms like simulated annealing, genetic search, and tabu search are out there and can be adapted to this problem.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .