The problem posed by Cohen [1] is the following: Given a finite set C of cookies, represented as Rugelach curves in a convex bounded subspace of 3-space, determine the subset S of maximal size such that the intersection of all curves in S is null. This is clearly a discrete optimization problem, and is thus solvable by the standard techniques of integer programming and cutting planes.

However looking more closely it is not difficult to see additional structure to the problem that perhaps makes it amenable to solution by dynamic programming or even the ubiquitous greedy algorithm. Shown effective for solving a related problem involving brownies by Basu [2], the greedy algorithm, which involves removing curves from the set one by one in order of size, seems ideal for this more difficult case as well, particularly as |C| is fairly large. Even if a proof of optimality is not directly forthcoming, it may be possible to obtain a near-optimal solution by trial and error.


[1] J. Cohen, "Tableware Set Theory and the Continuum Hyptothesis", 1996.
[2] J. Basu, "How to Eat Three Brownies at Once: Munch, Munch, Munch", 1996.

Return to Index