Circuit augmentation schemes are a family of combinatorial algorithms for linear programming that generalize the simplex method. To solve the linear program, they construct a so-called monotone circuit walk: They start at an initial vertex of the feasible region and traverse a discrete sequence of points on the boundary, while moving along certain allowed directions (circuits) and improving the objective function at each step until reaching an optimum. Since the existence of short circuit walks has been conjectured (Circuit Diameter Conjecture), several works have investigated how well one can efficiently approximate shortest monotone circuit walks towards an optimum. A first result addressing this question was given by De Loera, Kafer, and Sanita [SIAM J. Opt., 2022], who showed that given as input an LP and the starting vertex, finding a 2-approximation for this problem is NP-hard. Cardinal and the third author [Math. Prog. 2023] gave a stronger lower bound assuming the exponential time hypothesis, showing that even an approximation factor of \(O(\frac{\log m}{\log \log m})\) is intractable for LPs defined by \(m\) inequalities. Both of these results were based on reductions from highly degenerate polytopes in combinatorial optimization with high dimension.

One of the most elementary spreading models on graphs can be described by a fire spreading from a burning vertex in discrete time steps. At each step, all neighbors of burning vertices catch fire. A well-studied extension to model fire containment is to allow for fireproofing a number B of non-burning vertices at each step. Interestingly, basic computational questions about this model are computationally hard even on trees. One of the most prominent such examples is Resource Minimization for Fire Containment (RMFC), which asks how small B can be chosen so that a given subset of vertices will never catch fire. Despite recent progress on RMFC on trees, prior work left a significant gap in terms of its approximability. We close this gap by providing an optimal 2-approximation and an asymptotic PTAS, resolving two open questions in the literature. Both results are obtained in a unified way, by first designing a PTAS for a smooth variant of RMFC, which is obtained through a careful LP-guided enumeration procedure.

The (monotone) diameter of a polytope is a fundamental parameter with important connections to the efficiency of the simplex method. Despite the central role played by this parameter in discrete and linear optimization, determining the precise complexity of computing the diameter of an input polytope remains a long-standing open problem. In 1984 Frieze and Teng [FT94] proved the first cornerstone result in this direction by establishing that computing the diameter of an input polytope is weakly NP-hard. In a recent breakthrough- paper, Sanita (FOCS 2018, [San18]) studied the diameter of a special class of graph-based polytopes, known as fractional matching polytopes, and showed that determining their diameters is NP-hard, thus establishing strong NP-hardness of computing the diameter of polytopes.