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 Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-08 Page: https://delphi.science/r/arxiv/2611.11375 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…