{"id":"arxiv/2610.20422","url":"https://arxiv.org/abs/2610.20422","tags":["math.OC","cs.CC"],"score":0,"title":"On the Complexity of Linear Programs with Parametric Constraint Matrices","domain":"math.OC","source":"arxiv","authors":["Laurie Boveroux","Margarida Carvalho","Andrea Lodi","Quentin Louveaux"],"reviews":0,"subject":"math.OC","summary":"While sensitivity analysis for linear programs with parametric right- hand side vectors is well established, cases involving parametric constraint matrices remain less explored. To address this gap, we investigate linear programs where the constraint matrix depends linearly on a scalar parameter. Our goal is to compute the minimum and maximum optimal values of these parametric linear programs within a fixed parameter range. This corresponds to solving two bilevel programs. We show that both decision versions of these optimization problems are NP-complete by proving both NP-hardness and…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-14","reactions":{}}