A050296: Eating crow!

[Rob Pratt]

On Mon, 28 Oct 2002, John Layman wrote:

> Sometime over the weekend I realized that a blunder was likely in my
> calculations communicated last Friday, but email facilities were not available
> at the time.  I now see that Rob Pratt quickly uncovered my errors.
>
> Rob, your results are very impressive.  Would you be willing to make your
> algorithm available somehow?  If I use my original fail-proof algorithm
> (instead of my faulty efficient algorithm) I find that for n somewhere in the
> range of 35-50 the calculation takes longer than I'm willing to wait (days).
>
> John

I just used the following integer programming formulation, where the
decision variable x[i] is 1 if i is a member of the strongly triple-free
subset, 0 otherwise.

maximize sum {i in 1..n} x[i] subject to

x[i] + x[3i] <= 1 for i in 1..n such that 3i in 1..n

x[i] + x[2i] <= 1 for i in 1..n such that 2i in 1..n

x[i] in {0,1} for i in 1..n

The problem can also be thought of as finding a maximum independent set in
a graph with nodes 1..n and edges of the form (i,3i) and (i,2i).

Rob Pratt
Department of Operations Research
The University of North Carolina at Chapel Hill

rpratt at email.unc.edu

http://www.unc.edu/~rpratt/





MIME-Version: 1.0