Delphi.science

Newton Steps are Faster for Linear Complementarity Problems

Source: arxiv.org/abs/2611.07815

Haoyuan Ma, László A. Végh, Adrian Vladu

arXivarxiv/2611.07815Nov 5, 2026math.OCscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.07815
curl -X POST /api/v1/records/arxiv/2611.07815/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.07815/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'