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.

A mixed regular graph is a graph where every vertex has z incoming arcs, z outgoing arcs, and r edges. If in addition it has girth g , we say that the graph is a [z, r; g]-mixed graph. A [z, r; g]-mixed cage is a [z, r; g ]-mixed graph with the smallest number of vertices. We give constructions for mixed graphs with girth 5 and 6 using the incidence graph of projective planes. In particular, we present a family of [z, q; 5]-mixed graphs for a power of prime q ≥ 7 such that q - 1 ≤ 4z + R with z ≥ 1 and R ε {1,..., 5}. For girth 6, we present an infinite family for pairs of a prime q and a number p = q−1/2. If p is odd, the construction gives [p+1/2,q;6]-mixed graphs, otherwise we obtain [p/2,q;6]-mixed graphs.

We consider the Shortest Odd Path problem, where given an undirected graph G , a weight function on its edges, and two vertices s and t in G , the aim is to find an ( s , t ) -path with odd length and, among all such paths, of minimum weight. For the case when the weight function is conservative, i.e., when every cycle has non-negative total weight, the complexity of the Shortest Odd Path problem had been open for 20 years, and was recently shown to be NP -hard. We give a polynomial-time algorithm for the special case when the weight function is conservative and the set E − of negative-weight edges forms a single tree. Our algorithm exploits the strong connection between Shortest Odd Path and the problem of finding two internally vertex-disjoint paths between two terminals in an undirected edge-weighted graph. It also relies on solving an intermediary problem variant called Shortest Parity-Constrained Odd Path where for certain edges we have parity constraints on their position along the path. Also, we exhibit two FPT algorithms for solving Shortest Odd Path . The first FPT algorithm is parameterized by | E − | , the number of negative edges, or more generally, by the maximum size of a matching in the subgraph of G spanned by E − , when the weight function is conservative. Our second FPT algorithm is parameterized by the treewidth of G , and the algorithm does not rely on conservativeness.

We introduce a new class of inverse optimization problems in which an input solution is given together with k linear weight functions, and the goal is to modify the weights by the same deviation vector p so that the input solution becomes optimal with respect to each of them, while minimizing ‖p‖1. In particular, we concentrate on three problems with multiple weight functions: the inverse shortest s−t path, the inverse bipartite perfect matching, and the inverse arborescence problems. Using LP duality, we give min–max characterizations for the ℓ1-norm of an optimal deviation vector. Furthermore, we show that the optimal p is not necessarily integral even when the weight functions are so, therefore computing an optimal solution is significantly more difficult than for the single-weighted case. We also give a necessary and sufficient condition for the existence of an optimal deviation vector that changes the values only on the elements of the input solution, thus giving a unified understanding of previous results on arborescences and matchings.