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.

We consider the Stochastic Boolean Function Evaluation (SBFE) problem in the well-studied case of $k$-of-$n$ functions: There are independent Boolean random variables $x_1,\dots,x_n$ where each variable $i$ has a known probability $p_i$ of taking value $1$, and a known cost $c_i$ that can be paid to find out its value. The value of the function is $1$ iff there are at least $k$ $1$s among the variables. The goal is to efficiently compute a strategy that, at minimum expected cost, tests the variables until the function value is determined. While an elegant polynomial-time exact algorithm is known when tests can be made adaptively, we focus on the non-adaptive variant, for which much less is known. First, we show a clean and tight lower bound of $2$ on the adaptivity gap, i.e., the worst-case multiplicative loss in the objective function caused by disallowing adaptivity, of the problem. This improves the tight lower bound of $3/2$ for the unit-cost variant. Second, we give a PTAS for computing the best non-adaptive strategy in the unit-cost case, the first PTAS for an SBFE problem. At the core, our scheme establishes a novel notion of two-sided dominance (w.r.t. the optimal solution) by guessing so-called milestone tests for a set of carefully chosen buckets of tests. To turn this technique into a polynomial-time algorithm, we use a decomposition approach paired with a random-shift argument. In fact, our PTAS extends to the class of arbitrary symmetric Boolean functions, which are Boolean functions whose value only depends on the number of $1$s among the input variables.