This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Linderoth, J. Articles by Thain, G.

Improving Bounds on the Football Pool Problem by Integer Programming and High-Throughput Computing

Department of Industrial and Systems Engineering, University of Wisconsin–Madison, Madison, Wisconsin 53706
Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Department of Computer Science, University of Wisconsin–Madison, Madison, Wisconsin 53706
linderoth{at}wisc.edu
fmargot{at}andrew.cmu.edu
gthain{at}cs.wisc.edu

The football pool problem, which gets its name from a lottery-type game where participants predict the outcome of soccer matches, is to determine the smallest covering code of radius 1 of ternary words of length v. For v = 6, the optimal solution is not known. Using a combination of isomorphism pruning, subcode enumeration, and linear programming-based bounding, running on a high-throughput computational grid consisting of thousands of processors, we are able to improve the lower bound on the size of the optimal code from 65 to 71.

Key words: football pool problem; high-throughput computing; branch and bound; Condor; master-worker
History: received October 2007; revised December 2008; accepted March 2009.