Mechanism design without money has a rich history in social choice literature. Due to the strong impossibility theorem by Gibbard and Satterthwaite, exploring domains in which there exist dominant strategy mechanisms is one of the central questions in the field. We propose a general framework, called the generalized packing problem (\gpp), to study the mechanism design questions without payment. The \gpp\ possesses a rich structure and comprises a number of well-studied models as special cases, including, e.g., matroid, matching, knapsack, independent set, and the generalized assignment problem. We adopt the agenda of approximate mechanism design where the objective is to design a truthful (or strategyproof) mechanism without money that can be implemented in polynomial time and yields a good approximation to the socially optimal solution. We study several special cases of \gpp, and give constant approximation mechanisms for matroid, matching, knapsack, and the generalized assignment problem. Our result for generalized assignment problem solves an open problem proposed in \cite{DG10}. Our main technical contribution is in exploitation of the approaches from stable matching, which is a fundamental solution concept in the context of matching marketplaces, in application to mechanism design. Stable matching, while conceptually simple, provides a set of powerful tools to manage and analyze self-interested behaviors of participating agents. Our mechanism uses a stable matching algorithm as a critical component and adopts other approaches like random sampling and online mechanisms. Our work also enriches the stable matching theory with a new knapsack constrained matching model.

This paper considers a framework for combinatorial variants of perpetual-scheduling problems. Given an independence system (E,ℐ), a schedule consists of an independent set I_t ∈ ℐ for every time step t ∈ ℕ, with the objective of fulfilling frequency requirements on the occurrence of elements in E. We focus specifically on combinatorial bamboo garden trimming, where elements accumulate height at growth rates g(e) for e ∈ E and are reset to zero when scheduled, with the goal of minimizing the maximum height attained by any element. We assume that g is normalized so that it is a convex combination of the incidence vectors of ℐ. Using the integrality of the matroid-intersection polytope, we prove that, when (E,ℐ) is a matroid, it is possible to guarantee a maximum height of at most 2, which is optimal. We complement this existential result with efficient algorithms for specific matroid classes, achieving a maximum height of 2 for uniform and partition matroids, and 4 for graphic and laminar matroids. In contrast, we show that for general independence systems, the optimal guaranteed height is Θ(log |E|) and can be achieved by an efficient algorithm. For combinatorial pinwheel scheduling, where each element e ∈ E needs to occur in the schedule at least every a_e ∈ ℕ time steps, our results imply bounds on the density sufficient for schedulability.

For an arrangement \(\mathcal{H}\) of hyperplanes in \(\mathbb{R}^n\) through the origin, a region is a connected subset of \(\mathbb{R}^n \setminus \mathcal{H}\). The graph of regions \(G(\mathcal{H})\) has a vertex for every region, and an edge between any two vertices whose corresponding regions are separated by a single hyperplane from \(\mathcal{H}\). We aim to compute a Hamiltonian path or cycle in the graph \(G(\mathcal{H})\), i.e., a path or cycle that visits every vertex (=region) exactly once. Our first main result is that if \(\mathcal{H}\) is a supersolvable arrangement, then the graph of regions \(G(\mathcal{H})\) has a Hamiltonian cycle. More generally, we consider quotients of lattice congruences of the poset of regions \(\mathsf{P}(\mathcal{H}, R_0)\), obtained by orienting the graph \(G(\mathcal{H})\) away from a particular base region \(R_0\). Our second main result is that if \(\mathcal{H}\) is supersolvable and \(R_0\) is a canonical base region, then for any lattice congruence \(\equiv\) on \(\mathsf{P}(\mathcal{H}, R_0) =: L\), the cover graph of the quotient lattice \(L/{\equiv}\) has a Hamiltonian path.

An elimination tree for a connected graph \(G\) is a rooted tree on the vertices of \(G\) obtained by choosing a root \(x\) and recursing on the connected components of \(G-x\) to produce the subtrees of \(x\) . Elimination trees appear in many guises in computer science and discrete mathematics, and they encode many interesting combinatorial objects, such as bitstrings, permutations and binary trees. We apply the recent Hartung–Hoang–Mütze–Williams combinatorial generation framework to elimination trees and prove that all elimination trees for a chordal graph \(G\) can be generated by tree rotations using a simple greedy algorithm. This yields a short proof for the existence of Hamilton paths on graph associahedra of chordal graphs. Graph associahedra are a general class of high-dimensional polytopes introduced by Carr, Devadoss, and Postnikov, whose vertices correspond to elimination trees and whose edges correspond to tree rotations. As special cases of our results, we recover several classical Gray codes for bitstrings, permutations and binary trees, and we obtain a new Gray code for partial permutations. Our algorithm for generating all elimination trees for a chordal graph \(G\) can be implemented in time \({\mathcal{O}}(\sigma)\) on average per generated elimination tree, where \(\sigma=\sigma(G)\) denotes the maximum number of edges of an induced star in \(G\) . If \(G\) is a tree, we improve this to a loopless algorithm running in time \({\mathcal{O}}(1)\) per generated elimination tree. We also prove that our algorithm produces a Hamilton cycle on the graph associahedron of \(G\) , rather than just Hamilton path, if the graph \(G\) is chordal and 2-connected. Moreover, our algorithm characterizes chordality, i.e., it computes a Hamilton path on the graph associahedron of \(G\) if and only if \(G\) is chordal.

We show that all invertible n × n matrices over any finite field 𝔽_q can be generated in a Gray code fashion. More specifically, there exists a listing such that (1) each matrix appears exactly once, and (2) two consecutive matrices differ by adding or subtracting one row from a previous or subsequent row, or by multiplying or dividing a row by the generator of the multiplicative group of 𝔽_q. This even holds in the more general setting where the pairs of rows that can be added or subtracted are specified by an arbitrary transition tree that has to satisfy some mild constraints. Moreover, we can prescribe the first and the last matrix if n ≥ 3, or n = 2 and q > 2. In other words, the corresponding flip graph on all invertible n × n matrices over 𝔽_q is Hamilton connected if it is not a cycle. This solves yet another special case of Lovász conjecture on Hamiltonicity of vertex-transitive graphs.

Abstract. In this paper, we present a new framework that exploits combinatorial optimization for efficiently generating a large variety of combinatorial objects based on graphs, matroids, posets, and polytopes. Our method is based on a simple and versatile algorithm for computing a Hamilton path on the skeleton of a 0/1-polytope [Formula: see text], where [Formula: see text]. The algorithm uses as a black box any algorithm that solves a variant of the classical linear optimization problem [Formula: see text], and the resulting delay, i.e., the running time per visited vertex on the Hamilton path, is larger than the running time of the optimization algorithm only by a factor of [Formula: see text]. When [Formula: see text] encodes a particular class of combinatorial objects, then traversing the skeleton of the polytope [Formula: see text] along a Hamilton path corresponds to listing the combinatorial objects by local change operations; i.e., we obtain Gray code listings. As concrete results of our general framework, we obtain efficient algorithms for generating all ([Formula: see text]-optimal) bases and independent sets in a matroid; ([Formula: see text]-optimal) spanning trees, forests, matchings, maximum matchings, and [Formula: see text]-optimal matchings in a graph; vertex covers, minimum vertex covers, [Formula: see text]-optimal vertex covers, stable sets, maximum stable sets, and [Formula: see text]-optimal stable sets in a bipartite graph; as well as antichains, maximum antichains, [Formula: see text]-optimal antichains, and [Formula: see text]-optimal ideals of a poset. Specifically, the delay and space required by these algorithms are polynomial in the size of the matroid ground set, graph, or poset, respectively. Furthermore, all of these listings correspond to Hamilton paths on the corresponding combinatorial polytopes, namely the base polytope, matching polytope, vertex cover polytope, stable set polytope, chain polytope, and order polytope, respectively. As another corollary from our framework, we obtain an [Formula: see text] delay algorithm for the vertex enumeration problem on 0/1-polytopes [Formula: see text], where [Formula: see text] and [Formula: see text], and [Formula: see text] is the time needed to solve the linear program [Formula: see text]. This improves upon the 25-year-old [Formula: see text] delay algorithm due to Bussieck and Lübbecke.

We study the two-dimensional geometric knapsack problem for convex polygons. Given a set of weighted convex polygons and a square knapsack, the goal is to select the most profitable subset of the given polygons that fits non-overlappingly into the knapsack. We allow to rotate the polygons by arbitrary angles. We present a quasi-polynomial time O (1)-approximation algorithm for the general case and a pseudopolynomial time O (1)-approximation algorithm if all input polygons are triangles, both assuming polynomially bounded integral input data. Additionally, we give a quasi-polynomial time algorithm that computes a solution of optimal weight under resource augmentation—that is, we allow to increase the size of the knapsack by a factor of 1+δ for some δ > 0 but compare ourselves with the optimal solution for the original knapsack. To the best of our knowledge, these are the first results for two-dimensional geometric knapsack in which the input objects are more general than axis-parallel rectangles or circles and in which the input polygons can be rotated by arbitrary angles.

In this paper, we present a new framework that exploits combinatorial optimization for efficiently generating a large variety of combinatorial objects based on graphs, matroids, posets and polytopes. Our method relies on a simple and versatile algorithm for computing a Hamilton path on the skeleton of any 0/1-polytope $\operatorname{conv}(X)$, where $X \subseteq\{0,1\}^{n}$. The algorithm uses as a black box any algorithm that solves a variant of the classical linear optimization problem $\min \{w \cdot x \mid x \in X\}$, and the resulting delay, i.e., the running time per visited vertex on the Hamilton path, is only by a factor of $\log n$ larger than the running time of the optimization algorithm. When X encodes a particular class of combinatorial objects, then traversing the skeleton of the polytope $\operatorname{conv}(X)$ along a Hamilton path corresponds to listing the combinatorial objects by local change operations, i.e., we obtain Gray code listings. As concrete results of our general framework, we obtain efficient algorithms for generating all (c-optimal) bases and independent sets in a matroid; (c-optimal) spanning trees, forests, matchings, maximum matchings, and c-optimal matchings in a general graph; vertex covers, minimum vertex covers, c-optimal vertex covers, stable sets, maximum stable sets and c-optimal stable sets in a bipartite graph; as well as antichains, maximum antichains, c-optimal antichains, and c-optimal ideals of a poset. Specifically, the delay and space required by these algorithms are polynomial in the size of the matroid ground set, graph, or poset, respectively. Furthermore, all of these listings correspond to Hamilton paths on the corresponding combinatorial polytopes, namely the base polytope, matching polytope, vertex cover polytope, stable set polytope, chain polytope and order polytope, respectively. As another corollary from our framework, we obtain an $\mathcal{O}\left(t_{\text{LP}} \log n\right)$ delay algorithm for the vertex enumeration problem on 0/1-polytopes $\left\{x \in \mathbb{R}^{n} \mid A x \leq b\right\}$, where $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^{m}$, and $t_{\text{LP}}$ is the time needed to solve the linear program $\min \{w \cdot x \mid A x \leq b\}$. This improves upon the 25-year old $\mathcal{O}\left(t_{\text{LP}} n\right)$ delay algorithm due to Bussieck and Lübbecke.

In 1993, Savage, Squire, and West described an inductive construction for generating every acyclic orientation of a chordal graph exactly once, flipping one arc at a time. We provide two generalizations of this result. Firstly, we describe Gray codes for acyclic orientations of hypergraphs that satisfy a simple ordering condition, which generalizes the notion of perfect elimination order of graphs. This unifies the Savage-Squire-West construction with a recent algorithm for generating elimination trees of chordal graphs (SODA 2022). Secondly, we consider quotients of lattices of acyclic orientations of chordal graphs, and we provide a Gray code for them, addressing a question raised by Pilaud (FPSAC 2022). This also generalizes a recent algorithm for generating lattice congruences of the weak order on the symmetric group (SODA 2020). Our algorithms are derived from the Hartung-Hoang-Mutze-Williams combinatorial generation framework, and they yield simple algorithms for computing Hamilton paths and cycles on large classes of polytopes, including chordal nestohedra and quotientopes. In particular, we derive an efficient implementation of the Savage-Squire-West construction. Along the way, we give an overview of old and recent results about the polyhedral and order-theoretic aspects of acyclic orientations of graphs and hypergraphs. * Arturo Merino was supported by ANID Becas Chile 2019-72200522. Torsten Mütze was supported by Czech Science Foundation grant GA 22-15272S. Arturo Merino and Torsten Mütze were also supported by German Science Foundation grant 413902284.

For integers ‍k≥ 1 and n≥ 2k+1, the Kneser graph ‍K(n,k) has as vertices all k-element subsets of an n-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph ‍K(5,2). This problem received considerable attention in the literature, including a recent solution for the sparsest case n=2k+1. The main contribution of this paper is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph ‍J(n,k,s) has as vertices all k-element subsets of an n-element ground set, and an edge between any two sets whose intersection has size exactly ‍s. Clearly, we have K(n,k)=J(n,k,0), i.e., generalized Johnson graph include Kneser graphs as a special case. Our results imply that all known families of vertex-transitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász’ conjecture on Hamilton cycles in vertex-transitive graphs from ‍1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway’s Game of Life, and to analyze this system combinatorially and via linear algebra.

Abstract A generic rectangulation is a partition of a rectangle into finitely many interior-disjoint rectangles, such that no four rectangles meet in a point. In this work we present a versatile algorithmic framework for exhaustively generating a large variety of different classes of generic rectangulations. Our algorithms work under very mild assumptions, and apply to a large number of rectangulation classes known from the literature, such as generic rectangulations, diagonal rectangulations, 1-sided/area-universal, block-aligned rectangulations, and their guillotine variants, including aspect-ratio-universal rectangulations. They also apply to classes of rectangulations that are characterized by avoiding certain patterns, and in this work we initiate a systematic investigation of pattern avoidance in rectangulations. Our generation algorithms are efficient, in some cases even loopless or constant amortized time, i.e., each new rectangulation is generated in constant time in the worst case or on average, respectively. Moreover, the Gray codes we obtain are cyclic, and sometimes provably optimal, in the sense that they correspond to a Hamilton cycle on the skeleton of an underlying polytope. These results are obtained by encoding rectangulations as permutations, and by applying our recently developed permutation language framework.

Abstract. In 1993, Savage, Squire, and West described an inductive construction for generating every acyclic orientation of a chordal graph exactly once, flipping one arc at a time. We provide two generalizations of this result. First, we describe Gray codes for acyclic orientations of hypergraphs that satisfy a simple ordering condition, which generalizes the notion of perfect elimination order of graphs. This unifies the Savage–Squire–West construction with a recent algorithm for generating elimination trees of chordal graphs. Second, we consider quotients of lattices of acyclic orientations of chordal graphs, and we provide a Gray code for them, addressing a question raised by Pilaud. This also generalizes a recent algorithm for generating lattice congruences of the weak order on the symmetric group. Our algorithms are derived from the Hartung–Hoang–Mütze–Williams combinatorial generation framework, and they yield simple algorithms for computing Hamilton paths and cycles on large classes of polytopes, including chordal nestohedra and quotientopes. In particular, we derive an efficient implementation of the Savage–Squire–West construction. Along the way, we give an overview of old and recent results about the polyhedral and order-theoretic aspects of acyclic orientations of graphs and hypergraphs.

We say that a Hamilton cycle $C=(x_1,\ldots,x_n)$ in a graph $G$ is $k$-symmetric, if the mapping $x_i\mapsto x_{i+n/k}$ for all $i=1,\ldots,n$, where indices are considered modulo $n$, is an automorphism of $G$. In other words, if we lay out the vertices $x_1,\ldots,x_n$ equidistantly on a circle and draw the edges of $G$ as straight lines, then the drawing of $G$ has $k$-fold rotational symmetry, i.e., all information about the graph is compressed into a $360^\circ/k$ wedge of the drawing. The maximum $k$ for which there exists a $k$-symmetric Hamilton cycle in $G$ is referred to as the Hamilton compression of $G$. We investigate the Hamilton compression of four different families of vertex-transitive graphs, namely hypercubes, Johnson graphs, permutahedra and Cayley graphs of abelian groups. In several cases we determine their Hamilton compression exactly, and in other cases we provide close lower and upper bounds. The constructed cycles have a much higher compression than several classical Gray codes known from the literature. Our constructions also yield Gray codes for bitstrings, combinations and permutations that have few tracks and/or that are balanced.

An elimination tree for a connected graph G is a rooted tree on the vertices of G obtained by choosing a root x and recursing on the connected components of G–x to produce the subtrees of x. Elimination trees appear in many guises in computer science and discrete mathematics, and they encode many interesting combinatorial objects, such as bitstrings, permutations and binary trees. We apply the recent Hartung-Hoang-Mütze-Williams combinatorial generation framework to elimination trees, and prove that all elimination trees for a chordal graph G can be generated by tree rotations using a simple greedy algorithm. This yields a short proof for the existence of Hamilton paths on graph associahedra of chordal graphs. Graph associahedra are a general class of high-dimensional polytopes introduced by Carr, Devadoss, and Postnikov, whose vertices correspond to elimination trees and whose edges correspond to tree rotations. As special cases of our results, we recover several classical Gray codes for bitstrings, permutations and binary trees, and we obtain a new Gray code for partial permutations. Our algorithm for generating all elimination trees for a chordal graph G can be implemented in time (m + n) per generated elimination tree, where m and n are the number of edges and vertices of G, respectively. If G is a tree, we improve this to a loopless algorithm running in time (1) per generated elimination tree. We also prove that our algorithm produces a Hamilton cycle on the graph associahedron of G, rather than just Hamilton path, if the graph G is chordal and 2-connected. Moreover, our algorithm characterizes chordality, i.e., it computes a Hamilton path on the graph associahedron of G if and only if G is chordal.

Given integers $k\geq 2$ and $a_1,\ldots,a_k\geq 1$, let $\boldsymbol{a}:=(a_1,\ldots,a_k)$ and $n:=a_1+\cdots+a_k$. An $\boldsymbol{a}$-multiset permutation is a string of length $n$ that contains exactly $a_i$ symbols $i$ for each $i=1,\ldots,k$. In this work we consider the problem of exhaustively generating all $\boldsymbol{a}$-multiset permutations by star transpositions, i.e., in each step, the first entry of the string is transposed with any other entry distinct from the first one. This is a far-ranging generalization of several known results. For example, it is known that permutations ($a_1=\cdots=a_k=1$) can be generated by star transpositions, while combinations ($k=2$) can be generated by these operations if and only if they are balanced ($a_1=a_2$), with the positive case following from the middle levels theorem. To understand the problem in general, we introduce a parameter $Δ(\boldsymbol{a}):=n-2\max\{a_1,\ldots,a_k\}$ that allows us to distinguish three different regimes for this problem. We show that if $Δ(\boldsymbol{a})<0$, then a star transposition Gray code for $\boldsymbol{a}$-multiset permutations does not exist. We also construct such Gray codes for the case $Δ(\boldsymbol{a})>0$, assuming that they exist for the case $Δ(\boldsymbol{a})=0$. For the case $Δ(\boldsymbol{a})=0$ we present some partial positive results. Our proofs establish Hamilton-connectedness or Hamilton-laceability of the underlying flip graphs, and they answer several cases of a recent conjecture of Shen and Williams. In particular, we prove that the middle levels graph is Hamilton-laceable.

The well-known middle levels conjecture asserts that for every integer $n\geq 1$, all binary strings of length 2(n+1) with exactly n+1 many 0s and 1s can be ordered cyclically so that any two consecutive strings differ in swapping the first bit with a complementary bit at some later position. In his book The Art of Computer Programming, Knuth raised a stronger form of this conjecture (Problem 56 in section 7.2.1.3), which requires that the sequence of positions with which the first bit is swapped in each step of such an ordering has 2n+1 blocks of the same length, and each block is obtained by adding s=1 (modulo 2n+1) to the previous block. In this work, we prove Knuth's conjecture in a more general form, allowing for arbitrary shifts $s\geq 1$ that are coprime to 2n+1. We also present an algorithm to compute this ordering, generating each new bitstring in $\mathcal{O}(n)$ time, using $\mathcal{O}(n)$ memory in total.

A generic rectangulation is a partition of a rectangle into finitely many interior-disjoint rectangles, such that no four rectangles meet in a point. In this work we present a versatile algorithmic framework for exhaustively generating a large variety of different classes of generic rectangulations. Our algorithms work under very mild assumptions, and apply to a large number of rectangulation classes known from the literature, such as generic rectangulations, diagonal rectangulations, 1-sided/area-universal, block-aligned rectangulations, and their guillotine variants. They also apply to classes of rectangulations that are characterized by avoiding certain patterns, and in this work we initiate a systematic investigation of pattern avoidance in rectangulations. Our generation algorithms are efficient, in some cases even loopless or constant amortized time, i.e., each new rectangulation is generated in constant time in the worst case or on average, respectively. Moreover, the Gray codes we obtain are cyclic, and sometimes provably optimal, in the sense that they correspond to a Hamilton cycle on the skeleton of an underlying polytope. These results are obtained by encoding rectangulations as permutations, and by applying our recently developed permutation language framework.

The well-known middle levels conjecture asserts that for every integer n ≥ 1, all binary strings of length 2(n + 1) with exactly n + 1 many 0s and 1s can be ordered cyclically so that any two consecutive strings differ in swapping the first bit with a complementary bit at some later position. In his book ‘The Art of Computer Programming Vol. 4A’ Knuth raised a stronger form of this conjecture (Problem 56 in Section 7.2.1.3), which requires that the sequence of positions with which the first bit is swapped in each step of such an ordering has 2n + 1 blocks of the same length, and each block is obtained by adding s = 1 (modulo 2n + 1) to the previous block. In this work, we prove Knuth's conjecture in a more general form, allowing for arbitrary shifts s ≥ 1 that are coprime to 2n + 1. We also present an algorithm to compute this ordering, generating each new bitstring in (n) time, using (n) memory in total.

We study the two-dimensional geometric knapsack problem for convex polygons. Given a set of weighted convex polygons and a square knapsack, the goal is to select the most profitable subset of the given polygons that fits non-overlappingly into the knapsack. We allow to rotate the polygons by arbitrary angles. We present a quasi-polynomial time $O(1)$-approximation algorithm for the general case and a polynomial time $O(1)$-approximation algorithm if all input polygons are triangles, both assuming polynomially bounded integral input data. Also, we give a quasi-polynomial time algorithm that computes a solution of optimal weight under resource augmentation, i.e., we allow to increase the size of the knapsack by a factor of $1+δ$ for some $δ>0$ but compare ourselves with the optimal solution for the original knapsack. To the best of our knowledge, these are the first results for two-dimensional geometric knapsack in which the input objects are more general than axis-parallel rectangles or circles and in which the input polygons can be rotated by arbitrary angles.

We study the minimum weight basis problem on matroid when elements' weights are uncertain. For each element we only know a set of possible values (an uncertainty area) that contains its real weight. In some cases there exist bases that are uniformly optimal, that is, they are minimum weight bases for every possible weight function obeying the uncertainty areas. In other cases, computing such a basis is not possible unless we perform some queries for the exact value of some elements. Our main result is a polynomial time algorithm for the following problem. Given a matroid with uncertainty areas and a query cost function on its elements, find the set of elements of minimum total cost that we need to simultaneously query such that, no matter their revelation, the resulting instance admits a uniformly optimal base. We also provide combinatorial characterizations of all uniformly optimal bases, when one exists; and of all sets of queries that can be performed so that after revealing the corresponding weights the resulting instance admits a uniformly optimal base.