{"ID":2867875,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.18073","arxiv_id":"2509.18073","title":"Pareto-Optimal Linear Programming","abstract":"Pareto-optimality plays a central role in evaluating the efficiency of solutions to allocation problems, such as house allocation, school choice, and kidney exchange. We introduce a general linear programming problem subject to Pareto-optimality conditions, which we call Max-Pareto. Using the novel result that Pareto-optimal bipartite matchings are fractionally Pareto-optimal, we prove that Max-Pareto is $\\mathcal{NP}$-complete. We propose a bilinear programming formulation of Max-Pareto, and evaluate its computational performance on the problem of finding Pareto-optimal allocations of highest welfare.","short_abstract":"Pareto-optimality plays a central role in evaluating the efficiency of solutions to allocation problems, such as house allocation, school choice, and kidney exchange. We introduce a general linear programming problem subject to Pareto-optimality conditions, which we call Max-Pareto. Using the novel result that Pareto-o...","url_abs":"https://arxiv.org/abs/2509.18073","url_pdf":"https://arxiv.org/pdf/2509.18073v1","authors":"[\"Bart van Rossum\",\"Twan Dollevoet\"]","published":"2025-09-22T17:54:14Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}