{"id":"arxiv/2608.21574","url":"https://arxiv.org/abs/2608.21574","tags":["math.OC"],"score":0,"title":"The complexity landscape of robust (integer) linear programming","domain":"math.OC","source":"arxiv","authors":["Michael Poss","Jannis Kurtz","Marc Goerigk","Dorothee Henke"],"reviews":0,"subject":"math.OC","summary":"We study the computational complexity of the decision versions of three classic robust optimization problems: static robust optimization, two-stage (adjustable) robust optimization, and $K$-adaptability. We consider that the feasibility, uncertainty, and recourse sets are polyhedra or integer-programming-representable sets, the uncertainty is decision-independent or decision-dependent, and the feasible regions are bounded or unbounded. While these problems are well-established in the current literature, we give a systematic classification that places the resulting problems in $\\mathsf{P}$,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-21","reactions":{}}