{"id":"arxiv/2611.14837","url":"https://arxiv.org/abs/2611.14837","tags":["math.OC","cs.CC","cs.DS"],"score":0,"title":"Two-Stage Mixed-Integer Quadratic Programming in Polynomial Time","domain":"math.OC","source":"arxiv","authors":["Alberto Del Pia"],"reviews":0,"subject":"math.OC","summary":"Lenstra showed that mixed-integer linear programming can be solved in polynomial time when the number of integer variables is fixed and the number of continuous variables is arbitrary. Mixed-integer quadratic programming (MIQP) can be solved in polynomial time when the total number of variables is fixed. However, since MIQP is NP-hard already without integer variables, the analog of Lenstra's result fails unless P = NP. Hence, polynomial-time algorithms for MIQP with an arbitrary number of continuous variables must exploit additional structure. We study MIQPs with two-stage structure, which…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-10","reactions":{}}