The peaceable queens problem asks to determine the maximum number such that there is a placement of white queens and black queens on an chessboard so that no queen can capture any queen of the opposite color. In this paper, we consider the peaceable queens problem and its variant on the toroidal board. For the regular board, we show that , for all sufficiently large . This improves on the bound of van Bommel and MacEachern [16]. For the toroidal board, we provide new upper and lower bounds. Somewhat surprisingly, our bounds show that there is a sharp contrast in behaviour between the odd torus and the even torus. Our lower bounds are given by explicit constructions. For the upper bounds, we formulate the problem as a non-linear optimization problem with at most 100 variables, regardless of the size of the board. We solve our non-linear program exactly using modern optimization software. We also provide a local search algorithm and a software implementation which converges very rapidly to solutions which appear optimal. Our algorithm is sufficiently robust that it works on both the regular and toroidal boards. For example, for the regular board, the algorithm quickly finds the so-called Ainley construction. Thus, our work provides some further evidence that the Ainley construction is indeed optimal. *Matthew Drescher was supported by the National Science Foundation under Grant #2127309 to the Computing Research Association for the CIFellows 2021 Project. This paper has been awarded the “Code and Data Available” and “Results Reproduced” badges as recognition that the author(s) have followed reproducibility principles. Code and data that allow readers to reproduce the results in this paper are available at https://doi.org/10.5281/zenodo.13787471. Participation in the ALENEX artifact evaluation phase was optional and performed at the request of the author(s).

We study the feedback vertex set problem in tournaments from the polyhedral point of view, and in particular we show that performing just one round of the Sherali–Adams hierarchy gives a relaxation with integrality gap 7/3. This allows us to derive a 7/3-approximation algorithm for the feedback vertex set problem in tournaments that matches the best deterministic approximation guarantee due to Mnich, Williams, and Végh, and is a simplification and runtime improvement of their approach.

We present an O (√opt)-approximation algorithm for the maximum leaf spanning arborescence problem, where opt is the number of leaves in an optimal spanning arborescence. The result is based upon an O (1)-approximation algorithm for a special class of directed graphs called willows. Incorporating the method for willow graphs as a subroutine in a local improvement algorithm gives the bound for general directed graphs.