The Football Pool Polytope

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 ha...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Marenco, J.L., Rey, P.A.
Formato: JOUR
Materias:
football pool
polyhedral combinatorics
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_15710653_v30_nC_p75_Marenco
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_15710653_v30_nC_p75_Marenco
record_format dspace
spelling todo:paper_15710653_v30_nC_p75_Marenco2023-10-03T16:27:02Z The Football Pool Polytope Marenco, J.L. Rey, P.A. football pool polyhedral combinatorics 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. Fil:Marenco, J.L. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_15710653_v30_nC_p75_Marenco
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic football pool
polyhedral combinatorics
spellingShingle football pool
polyhedral combinatorics
Marenco, J.L.
Rey, P.A.
The Football Pool Polytope
topic_facet football pool
polyhedral combinatorics
description 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.
format JOUR
author Marenco, J.L.
Rey, P.A.
author_facet Marenco, J.L.
Rey, P.A.
author_sort Marenco, J.L.
title The Football Pool Polytope
title_short The Football Pool Polytope
title_full The Football Pool Polytope
title_fullStr The Football Pool Polytope
title_full_unstemmed The Football Pool Polytope
title_sort football pool polytope
url http://hdl.handle.net/20.500.12110/paper_15710653_v30_nC_p75_Marenco
work_keys_str_mv AT marencojl thefootballpoolpolytope
AT reypa thefootballpoolpolytope
AT marencojl footballpoolpolytope
AT reypa footballpoolpolytope
_version_ 1782030395095646208

Ejemplares similares