{"id":"arxiv/2611.11375","url":"https://arxiv.org/abs/2611.11375","tags":["cs.CC","cs.DM","math.CO","math.OC"],"score":0,"title":"Linear Objective Problems: A Complexity Framework for Bilevel Optimization","domain":"cs.CC","source":"arxiv","authors":["Christoph Grüne","James B. Orlin","Lasse Wulf"],"reviews":0,"subject":"cs.CC","summary":"Many bilevel and robust optimization problems are complete for the second level of the polynomial hierarchy, but such results are usually proven one problem at a time with problem-specific reductions. A recurring obstacle is that the lower level must select an optimal solution rather than merely a feasible one, whereas standard reductions preserve only whether a solution exists, not which solutions are optimal. We introduce linear objective problems (LOP), a framework for optimization problems whose solutions are explicit subsets of a ground set and whose objective is linear in these…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-08","reactions":{}}