{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-05","reactions":{}}