Người báo cáo: Hoàng Anh Quân (Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội)
Thời gian: từ 9h sáng thứ 4 ngày 22.09.2021.
Tóm tắt: One-factorization of the complete graph $K_{2n}$ has been a challenging, attractive topic in combinatorics and operations research. A balanced tournament design (BTD) of order $n$ is a one-factorization of $K_{2n}$ which schedules $2n$ teams in a round-robin tournament lasting in $2n-1$ days with balanced constraints. In particular, there are $n$ matches taking place in $n$ stadiums simultaneously each day, and the balanced constraints ensure that every~team competes at each stadium at most twice. In this talk, we focus on the problem of finding a special type of BTD called starter balanced tournament design (SBTD) in which all one-factors are starters. We transform the problem into a binary ILP model and introduce insightful observations to reduce its complexity. We utilize Gurobi Optimizer to solve the model and obtain SBTDs in a large number of sizes with few gaps. It provides strong evidence that most likely SBTDs exist for almost all sizes. As a collateral benefit, we identify many new rainbow-colored Hamiltonian balanced tournament designs (HBTDs). |
