Conference Agenda

How many mutually non-attacking queens can be placed on a d-dimensional chessboard of size n? The n-queens problem in higher dimensions is a generalization of the well-known n-queens problem. We provide a comprehensive overview of theoretical results, bounds, solution methods, and the interconnectivity of the problem within topics of discrete optimization and combinatorics. We present an integer programming formulation of the n-queens problem in higher dimensions and several strengthenings through additional valid inequalities. Compared to recent benchmarks, we achieve a speedup in computational time between 15-70x over all instances of the integer programs. Our computational results prove optimality of certificates for several large instances. Breaking additional, previously unsolved instances with the proposed methods is likely possible. On the primal side, we further discuss heuristic approaches to constructing solutions that turn out to be optimal when compared to the IP. We conclude with preliminary results on the number and density of the solutions.

We consider a game-theoretic variant of maximizing a non-decreasing submodular function under a cardinality constraint. Initially, a solution to this classical problem is determined. Subsequently, a predetermined number of elements from the ground set, not necessarily contained in the initial solution, are deleted, potentially reducing the solution's cardinality. Afterwards, the current solution is expanded by adding available elements, adhering to the cardinality constraint. The objective is to maximize the value of the ultimate solution, with the deletion being maximally disadvantageous to the initial solution.

For M-natural-concave objective functions and any predetermined number of deleted elements, we show that the greedy algorithm returns an optimal solution. Assuming the deletion of exactly one element, we introduce an algorithm that yields an ultimate solution approximating the optimal ultimate solution to this problem by at least 0.5(1-1/e).

A classic result of Korte and Hausmann (1978) and Jenkyns (1976) bounds the quality of the greedy solution to the problem of finding a maximum value basis of an independence system (E,I) in terms of the rank-quotient.

We extend this result in two ways. First, we apply the greedy algorithm to an inner independence system contained in I. Additionally, following an idea of Milgrom (2017),

we incorporate exogenously given prior information about the set of likely candidates for an optimal basis in terms of a set. We provide a generalization of the rank-quotient that yields a tight bound on the worst-case performance of the greedy algorithm applied to the inner independence system relative to the optimal solution in O. Furthermore, we show that for a worst-case objective, the inner independence system approximation may outperform not only the standard greedy algorithm but also the inner matroid approximation.

Second, we generalize the inner approximation framework of independence systems to inner approximations of packing instances by inner polymatroids and inner packing instances. We consider the problem of maximizing a separable discrete concave function and show that our inner approximation can be better than the greedy algorithm applied to the original packing instance. Our result provides a lower bound to the generalized rank-quotient of a greedy algorithm to the optimal solution in this more general setting and subsumes Malinov and Kovalyov (1980). We apply the inner approximation approach to packing instances induced by the FCC incentive auction and by two knapsack constraints.