Artículo
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. © 2008 Elsevier B.V. All rights reserved.
Registro:
| Documento: | Artículo |
| Título: | The Football Pool Polytope |
| Autor: | Marenco, J.L.; Rey, P.A. |
| Filiación: | Computer Science Dept., FCEN, University of Buenos Aires, Argentina Departamento de Ingeniería Industrial, FCFM, Universidad de Chile, Chile |
| Palabras clave: | football pool; polyhedral combinatorics |
| Año: | 2008 |
| Volumen: | 30 |
| Número: | C |
| Página de inicio: | 75 |
| Página de fin: | 80 |
| DOI: | http://dx.doi.org/10.1016/j.endm.2008.01.014 |
| Título revista: | Electronic Notes in Discrete Mathematics |
| Título revista abreviado: | Electron. Notes Discrete Math. |
| ISSN: | 15710653 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v30_nC_p75_Marenco |
Referencias:
- Cohen, G., Honkala, I., Litsyn, S., Lobstein, A., (1997) Covering Codes, , North-Holland
- Balas, E., Ng, S., On the set covering polytope I: All the facets with coefficients in {0, 1, 2} (1989) Mathematical Programming, 43, pp. 57-69
- Kamps, H., van Lint, J., The football pool problem for 5 matches (1967) Journal of Combinatorial Theory, 2, pp. 315-325
- van Lint, J., (1982) Introduction to coding theory, , Springer-Verlag
- Östergard, P., A combinatorial proof of the football pool problem for six matches (1996) Journal of Combinatorial Theory, A-76, pp. 160-163
- Sánchez-García, M., Sobrón, M., Vitoriano, B., On the set covering polytope: Facets with coefficients in {0, 1, 2, 3} (1998) Annals of Operations Research, 81, pp. 343-356
Citas:
---------- APA ----------
Marenco, J.L. & Rey, P.A. (2008) . The Football Pool Polytope. Electronic Notes in Discrete Mathematics, 30(C), 75-80.http://dx.doi.org/10.1016/j.endm.2008.01.014
---------- CHICAGO ----------
Marenco, J.L., Rey, P.A. "The Football Pool Polytope" . Electronic Notes in Discrete Mathematics 30, no. C (2008) : 75-80.http://dx.doi.org/10.1016/j.endm.2008.01.014
---------- MLA ----------
Marenco, J.L., Rey, P.A. "The Football Pool Polytope" . Electronic Notes in Discrete Mathematics, vol. 30, no. C, 2008, pp. 75-80.http://dx.doi.org/10.1016/j.endm.2008.01.014
---------- VANCOUVER ----------
Marenco, J.L., Rey, P.A. The Football Pool Polytope. Electron. Notes Discrete Math. 2008;30(C):75-80.http://dx.doi.org/10.1016/j.endm.2008.01.014
