  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.
