We study the computational complexity of fairly allocating indivisible, mixed-manna items. For basic measures of fairness, this problem is hard in general. Ergo, research has flourished concerning input classes where efficient algorithms exist, both for the purpose of establishing theoretical boundaries and for the purposeof designing practical algorithms for real-world instances. Notably, the paradigm of fixed-parameter tractability~(FPT) has lead to new insights and improved algorithms for a variety of fair allocation problems; see, for example, Bleim at al. (IJCAI’16), Aziz et al. (AAAI’17), Bredereck et al. (EC'19) and Kulkarni et al. (EC’21).

Our focus is the fairness measure {\em maximin shares} (MMS). Motivated by the general non-existence of MMS allocations, Aziz et al. (AAAI’17) studied {\em optimal MMS allocations}, namely solutions that achieve the best alpha-approximation for the maximin share value of every agent. These allocations are guaranteed to exist, prompting the important open question of whether optimal MMS allocations can be computed efficiently. We answer this question affirmatively by providing FPT algorithms to output optimal MMS allocations. Furthermore, our techniques extend to find allocations that optimize alternative objectives, such as minimizing the additive approximation, and maximizing some variants of global welfare.

In fact, all our algorithms are designed for a more general MMS problem in machine scheduling. Here, each mixed-manna item (job) must be assigned to an agent (machine) and has a processing time and a deadline. This generalization is of independent interest as it induces models for important applications such as ride-hailing services and shift scheduling. We develop efficient algorithms running in time FPT. Formally, we present polynomial time algorithms w.r.t. the input size multiplied by some function dependent on the parameters that yield optimal maximin-value approximations (among others) when parameterized by
(i) the number of items,
(ii) the maximum number of items in any group (which will be assigned independently), the number of agents, and the maximum absolute utility value,
(iii) the number of agents, the number of different deadlines, the maximum processing time, and the maximum absolute utility value.

To obtain these results, we utilize machinery from integer programming. In particular, we employ the framework of n-fold integer programs -- these are integer programs with a specific structure that allows them to be solved in time FPT. Our results are tight. We prove that any stronger parameterization is NP-hard even if the parameters only have constant value. Hence, under common complexity theoretical assumptions, there exists no FPT time algorithm. Consequently, this work gives a complete complexity theoretical picture and efficient algorithms for fairly allocating indivisible, mixed-manna items under the notion of maximin share fairness.

We consider a generalization of the stable set problem on mixed graphs. This adaptation enables the consideration of specific additional node relations which are expressed through directed arcs in the graph. Building upon previous research on the generalized stable set problem on mixed graphs, we investigate stable set problems on symmetric graphs. One common approach to handle symmetry in order to improve solution performance is via symmetry handling inequalities (SHIs). Choosing Schreier-Sims (SST) cuts as SHIs, we obtain inequalities that agree with the interpretation of directed edges in mixed graphs for the stable set problem. In the special case of undirected graphs with additional corresponding SST cuts, we demonstrate the simplification of the transformation of mixed graphs into closed mixed graphs. A central question that arises is how the addition of SST cuts influences the complexity of the stable set problem. In this context, we examine how SST cuts should be added to a trivially perfect graph such that the resulting mixed graph remains perfect and discuss different conditions.

We consider schedules for single round-robin tournaments on an even number of players, where each of the players plays every other player exactly once, either at home or away. We assume that the players are sorted on a predetermined ranking, where the first player is the strongest, and the last player is the weakest player of the competition. Such a ranking is sometimes directly available, such as with Elo rating scores for chess players, or can be derived from the final standings of previous editions of the tournament. With only one match between any pair of opponents, one team will have the asymmetric advantage of playing home (or in the case of chess, playing with white), which we consider as having positive effect on the match outcome for that player.

Designing schedules with desirable properties has received a lot of attention in the literature, such as minimizing the number of home and away breaks. Breaks are occurrences in the schedule where a player plays two home or two away matches in consecutive rounds. For each player, the home and away matches ordered by the round in which they are played, define a home/away pattern (HAP), which we refer to as a regular HAP.

Given a ranking of the players, we now also define a ranking HAP for each player, where the home and away matches for that player are ordered by the rank of their opponents. Intuitively, we want for a player to have the number of home and away matches balanced between opponents of a similar rank. For example, we consider it unfair for a player to play many home matches against top-ranked opponents, or to play many home matches against low-ranked opponents. We refer to this as ranking fairness. In this work, we define a ranking-fairness measure and show under which conditions a ranking-fair schedule, i.e., schedules that are optimal for the measure, can be obtained. Ranking-fair schedules exhibit several symmetries, which we exploit in integer programming formulations for finding such schedules, as well as in combinatorial arguments to prove or disprove existence for specific cases. In particular, we show when the number of players is a multiple of four, there exists a ranking-fair schedule that also has a minimum number of breaks.

A symmetry of a mixed-integer nonlinear program (MINLP) is a bijective map that transforms feasible solutions into feasible solutions while preserving the objective value. Already for linear problems it is well known that symmetries can negatively impact the performance of branch-and-bound methods, since symmetric regions of the search space will be repeatedly explored without providing new information. Most of the existing approaches for detecting symmetries focus on permutation symmetries that exchange the order of entries in a solution vector. For many problems classes, however, permutation symmetries do not capture all symmetries. For example, when packing objects into rectangular containers, also reflection symmetries of the container can be taken into account.

In this talk, we present a novel mechanism for computing, next to permutation symmetries, also reflection and translation symmetries of MINLPs. As existing approaches for permutation symmetries, we introduce a suitable graph whose automorphisms correspond to symmetries of a MINLP. Since reflection symmetries may nontrivially interact with nonlinear functions of a MINLP, however, our graph is much more involved than the previously known symmetry detection graphs. We also briefly discuss generalizations of state-of-the-art symmetry handling methods to reflection symmetries. The talk is concluded by numerical experiments showing the effect of handling reflection symmetries in the MINLP solver SCIP.