Distributing צדקה In Polynomial Time

This post was inspired by Andy, a former computer science guy, and is dedicated to Dr. Pinhas Grossman, Marie Curie Research Fellow at Cardiff University.

In the course of a conversation with a friend of mine who collects מתנות לאביונים for distribution to several אביונים, the following question arose:

A number of donors contribute arbitrary amounts of money for distribution by a גבאי to two עניים. Each donor prefers that his entire donation be given exclusively to one עני. What is the optimal distribution of the funds, that minimizes the difference between the sums received by the two עניים?

Solving this by brute force is straightforward; here’s a Perl program to do it:

[perl]#! /usr/bin/perl -w

# Copyright (C) 2010 Yitzhak (celejar@gmail.com)
# Combin is free software, released under the terms of the Perl Artistic
# License: http://perldoc.perl.org/perlartistic.html
# Combin comes with ABSOLUTELY NO WARRANTY

# Combin finds the division of a set of numbers into two subsets, such
# that the difference between the sums of the numbers in the subsets is
# the smallest possible

# usage: combin [-n num [-m max]] [-v]

# If -n is not given, a series of numbers is read from STDIN. Otherwise,
# ‘num’ random numbers between 1 and ‘max’ (or 1024, if -m is not given)
# are generated. If -v is specified, Combin will print out interim minimal
# solutions.

use strict;
no warnings ‘recursion’;

use Getopt::Std;

my (@vals, @sub_vals, $total, @best_sub_vals);
my %opts = (m => 1024);
getopts(‘n:m:v’, \%opts);
if ($opts{‘n’}) {for (my $i = 0; $i < $opts{'n'}; $i++) {push @vals, int(rand($opts{'m'})) + 1}} else {foreach (<>) {chomp; push @vals, $_} $opts{‘n’} = $#vals + 1}
foreach (@vals) {$total += $_}
my ($sub_total, $half, $best) = (0, int($total / 2), 0);
print “Total:\t$total\tHalf:\t$half\tValues:\t”, join(” “, @vals), “\n\n”;

sub rec {
my $i = shift;
if ($i == $opts{‘n’}) {

if ($sub_total > $best) {
print “Subtotal: $sub_total\tSubvals: @sub_vals\n” if $opts{‘v’};
$best = $sub_total;
@best_sub_vals = @sub_vals;
if ($sub_total == $half) {print “Ideal solution found – quitting.\n”; exit}
}
return;
}
rec($i + 1);
return if $sub_total + $vals[$i] > $half;
$sub_total += $vals[$i];
push @sub_vals, $vals[$i];
rec($i + 1);
$sub_total -= $vals[$i];
pop @sub_vals;
}

rec 0;

END {
print “Subtotal: $best\tSubvals: @best_sub_vals\n”
}
[/perl]

The problem, of course, is that this simplistic algorithm runs in exponential time, since we are basically taking each of n donations independently and making a binary decision about it. Indeed, the question of whether there exists an exact solution, where the two recipients each receive precisely the same amount, is known as the Partition Problem; it is a subset of the Subset Sum Problem, which is in turn a subset of the Knapsack Problem. These problems are apparently known to be in general NP-complete, and since the decision versions are NP-complete, the optimization versions are NP-hard.

In 2008, Jorma Jormakka proved that “there does not exist a polynomial-time
algorithm to the the subset sum problem.”

On the other hand, on April 1, 2009, Doron Zeilberger “provided a polynomial time algorithm for the Subset Sum problem”, but he subsequently had to clarify that “you should add that this was meant as an April Fool’s Joke, since apparently, some people didn’t get that it was meant as a joke”. One giveaway might have been this paragraph:

A considerable speed-up can be achieved if one uses “analog” computations, namely an analytical balance easily obtained in any chemistry laboratory. First have the computer plot the real and imaginary parts of P(e ^ ix ), above −π < x < π, on high-quality paper. Second, print-out these two plots. Third, using scissors, for each of these plots, carefully cut the parts above and below the x-axis. Third, find the difference in weight between the positive and negative parts, and divide by the weight of a unit square. If the sum of the absolute values of the two differences is less than √2/2, then output no, otherwise yes.

Incidentally, Zeilberger is also one of the authors of Talmudic lattice path counting:

Naive counting counts by 1, Generatingfunctionology counts by z**n, sieves count by +1 or -1, but the Talmud counts by fractions.

The paper begins as follows:

Two are holding a talit, one is saying it is all his, and (the other one) is saying it is all his, … let them each get half. (Bava Metzia)

Consider all planar walks, with positive unit steps (1,0) and (0,1), from the origin (0,0) to a given point (a,b). Let L be the line joining the beginning to the end, i.e. the line bx-ay=0. Call the region below L “downtown”, and the region above L “uptown”, the line L being the border-line between downtown and uptown. Each such walk has a+b-1 points, not counting the endpoints. For i=0, … ,a+b-1, let Wi be the set of walks with “exactly” i points downtown and “exactly” a+b-1-i points uptown. How do we treat those walks that have some points on L? If there are i points downtown, and j points on L, then each of the sets Wi , Wi+1 , … , Wi+j have equal claim for this walk. If it is possible to divide a talit, then why not divide a walk. After the j+1 contesting sets take oaths that they each own at least 1/(j+1) of the contested walk, we declare that each gets exactly 1/(j+1) of that walk. It turns out that this way of distributing border-line (sic!) walks is as fair as can be, since we have:

Theorem: The sets Wi, i=0, … , a+b-1 are equi-numerous. …

The paper contains this interesting little footnote:

The third author [Zeilberger] grew up in Kiryat Motzkin, that was named after Theodore Motzkin’s father, Leo, the great Zionist leader. There are at least two other examples of Zionist leaders whose sons became combinatorialists: Ze’ev Jabotinsky, whose son Eri, was a professor of Mathematics at the Technion, and Alex Wilf, whose son is Herb Wilf.

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *