We derive two hardness results on stable winning coalitions in Gamson’s game. First, it is coNP-complete to decide whether there exists a stable winning coalition that is connected. Secondly, it is <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$\Delta _2$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msub> <mi mathvariant="normal">Δ</mi> <mn>2</mn> </msub> </math> </EquationSource> </InlineEquation>P-complete to decide whether there exists a stable winning coalition...</equationsource></equationsource></inlineequation>

The x-and-y-axes travelling salesman problem forms a special case of the Euclidean TSP, where all cities are situated on the x-axis and on the y-axis of an orthogonal coordinate system of the Euclidean plane. By carefully analyzing the underlying combinatorial and geometric structures, we show...

We show that the following problem is NP-hard, and hence computationally intractable: "Given a vector y that Lorenz-dominates a vector x, what is the smallest number of Muirhead-Dalton transfers that transform x into y?"

We investigate a special case of the unbounded knapsack problem in which the item weights form an arithmetic sequence. We derive a polynomial time algorithm for this special case with running time O(n8), where n denotes the number of distinct items in the instance. Furthermore, we extend our...

We describe the two-to-one assignment problem, a problem in between the axial three-index assignment problem and the three-dimensional matching problem, having applications in various domains. For the (relevant) case of decomposable costs satisfying the triangle inequality we provide, on the...

The students of the Department of Industrial Design at the TU Eindhoven are allowed to design part of their curriculum by selecting courses from a huge course pool. They do this by handing in ordered preference lists with their favorite courses for the forthcoming time period. Based on this...

We characterize single-crossing preference profiles in terms of two forbidden substructures, one of which contains three voters and six (not necessarily distinct) alternatives, and one of which contains four voters and four (not necessarily distinct) alternatives. We also provide an efficient...

We describe the two-to-one assignment problem, a problem in between the axial three-index assignment problem and the three-dimensional matching problem, having applications in various domains. For the (relevant) case of decomposable costs satisfying the triangle inequality we provide, on the...