{"id":"arxiv/2606.11820","url":"https://arxiv.org/abs/2606.11820","tags":["math.OC","cs.DS"],"score":0,"title":"On finding exact solutions of linear programs in the oracle model","domain":"math.OC","source":"arxiv","authors":["Daniel Dadush","László A. Végh","Giacomo Zambelli"],"reviews":0,"subject":"math.OC","summary":"We consider linear programming in the oracle model: $\\max\\{c^\\top x \\,:\\, x\\in P\\}$, where the polyhedron $P=\\{x\\in\\mathbb{R}^n\\,:\\, Ax\\le b\\}$ is given by a separation oracle. We present an algorithm that finds exact primal and dual solutions using $O(n^2\\log(n/δ))$ oracle calls and $O(n^4\\log(n/δ)+n^5\\log\\log(1/δ))$ arithmetic operations, where $δ$ is a geometric condition number associated with the system $(A,b)$. These bounds do not depend on the cost vector $c$ and do not require a priori knowledge of $δ$. For rational data, $\\log(1/δ)$ is polynomially bounded in the encoding size of…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-10","reactions":{}}