{"id":"arxiv/2603.18551","url":"https://arxiv.org/abs/2603.18551","tags":["math.OC","cs.CC","cs.LG"],"score":0,"title":"Learning Decision-Sufficient Representations for Linear Optimization","domain":"math.OC","source":"arxiv","authors":["Yuhan Ye","Saurabh Amin","Asuman Ozdaglar"],"reviews":0,"subject":"math.OC","summary":"We study how to construct compressed datasets that suffice to recover optimal decisions in linear programs with an unknown cost vector $c$ lying in a prior set $\\mathcal{C}$. Recent work by Bennouna et al. provides an exact geometric characterization of sufficient decision datasets (SDDs) via an intrinsic decision-relevant dimension $d^\\star$. However, their algorithm for constructing minimum-size SDDs requires solving mixed-integer programs. In this paper, we establish hardness results showing that computing $d^\\star$ is NP-hard and deciding whether a dataset is globally sufficient is…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-19","reactions":{}}