1
$\begingroup$

I've been writing codes to solve a standard partition problem. I've investigated brute force, greedy, Karmarkar-Karp and complete Karmarkar-Karp algorithms.

Standard partition problem: divding a set into two subsets such that the difference between the sums of the subsets is minimized.

I'm also looking at a non-standard partition problem (this is my terminology)

Non-standard partition problem: divding a set into two subsets such that an arbitrary function of the sums of the subsets is minimized. In this case, furthermore, the set needn't be a set of reals, it could be e.g. a set of vectors.

In the special case in which the arbitrary function is $f(\sum_1, \sum_2)=|\sum_1- \sum_2|$, where $\sum_1$ is sum of subset one etc, the non-standard problem reduces to the standard problem.

At the moment, I can trivially generalise brute force and a greedy algorithm to the non-standard case. The former is slow and the latter incomplete and often poor, however.

Is there a better algorithm for this problem? I'm interested in complete and incomplete algorithms. Or is the problem just too general?

What if I make it even more general by permitting $f(s_1, s_2)$ to be minimised where $s$ denotes a subset, i.e. an arbitrary function of the subsets rather than the subsums.

$\endgroup$
  • 1
    $\begingroup$ I doubt you're going to get good algorithms if $f$ is truly arbitrary. I suspect you'll need $f$ to have some structure or helpful properties, if you want to achieve anything useful. Does $f$ have any structure? Any useful properties? Is it a distance metric? Monotone in each argument? Something else? $\endgroup$ – D.W. Dec 31 '15 at 3:58
  • $\begingroup$ @D.W. I'll update my q with a specific example, but I'm interested in the general case $\endgroup$ – innisfree Dec 31 '15 at 4:03
  • 1
    $\begingroup$ If you're interested in the general case, the answer is likely to be that there is no good algorithm for the general case. Don't bother with an example if you're only interested in the general case and you're not interested in an algorithm that's specialized to that example. $\endgroup$ – D.W. Dec 31 '15 at 4:04
  • $\begingroup$ @DW Well, I'm not (that) interested in it from an academic point of view - I was writing some codes that I wanted to be be pretty flexible for future use. But at the moment, I have one specific thing I'm calculating. $\endgroup$ – innisfree Jan 1 '16 at 8:10
  • $\begingroup$ What is "divding"? ​ ​ $\endgroup$ – user12859 Jan 4 '16 at 14:20

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.