Improved lower bounds for Queen's Domination via an exactly-solvable relaxation
| Autor: | Karandikar, Archit, Dutta, Akashnil |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | The Queen's Domination problem, studied for over 160 years, poses the following question: What is the least number of queens that can be arranged on a $m \times n$ chessboard so that they either attack or occupy every cell? We propose a novel relaxation of the Queen's Domination problem and show that it is exactly solvable on both square and rectangular chessboards. As a consequence, we improve on the best known lower bound for rectangular chessboards in $\approx 12.5\%$ of the non-trivial cases. As another consequence, we simplify and generalize the proofs for the best known lower-bounds for Queen's Domination of square $n \times n$ chessboards for $n \equiv \{0,1,2\} \mod 4$ using an elegant idea based on a convex hull. Finally, we show some results and make some conjectures towards the goal of simplifying the long complicated proof for the best known lower-bound for square boards when $n \equiv 3 \mod 4$ (and $n > 11$). These simple-to-state conjectures may also be of independent interest. Comment: 20 pages, 7 figures For associated repo, see https://github.com/architkarandikar/queens-domination |
| Databáze: | arXiv |
| Externí odkaz: |
|