Paper Info
Title
The Football Pool Polytope
Abstract
The football pool problem asks for the minimun number of bets on the result on n football matches ensuring that some bet correctly predicts the outcome of at least n−1 of them. This combinatorial problem has proven to be extremely difficult, and is open for n⩾6. Integer programming techniques have been applied to this problem in the past but, in order to tackle the open cases, a deep knowledge of the polytopes associated with the integer programs modeling this problem is required. In this work we address this issue, by defining and studying the football pool polytope in connection with a natural integer programming formulation of the football pool problem. We explore the basic properties of this polytope and present several classes of facet-inducing valid inequalities over natural combinatorial structures in the original problem.
Year
DOI
Venue
2008
10.1016/j.endm.2008.01.014
Electronic Notes in Discrete Mathematics
Keywords
Field
DocType
football pool,polyhedral combinatorics
Integer,Discrete mathematics,Football,Combinatorics,Polytope,Integer programming,Mathematics,Polyhedral combinatorics,Deep knowledge
Journal
Volume
ISSN
Citations 
30
1571-0653
0
PageRank 
References 
Authors
0.34
2
2
Name
Order
Citations
PageRank
Javier L. Marenco161.53
Pablo A. Rey2254.58