Id: arxiv/2611.07815 Url: https://arxiv.org/abs/2611.07815 Tags: math.OC, cs.DS Score: 0 Title: Newton Steps are Faster for Linear Complementarity Problems Domain: math.OC Source: arxiv Authors: Haoyuan Ma, László A. Végh, Adrian Vladu Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-11-05 Page: https://delphi.science/r/arxiv/2611.07815 Linear Complementarity Problems (LCPs) with sufficient matrices form a well-studied class of problems, dating back from the foundational works of Cottle and Dantzig (1968). LCPs capture convex quadratic programs, and admit reductions from problems such as discounted stochastic games or mean-payoff games. While the original approach for solving these problems was based on pivoting methods, in their 1991 book, Kojima, Megiddo, Noma, and Yoshise introduced an interior point method (IPM) with running time that is polynomial in the input size, but which depends linearly on a certain parameter…