betaFeedback

WorksMathematics

Newton Steps are Faster for Linear Complementarity Problems

Abstract

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 called the handicap number of the matrix. Despite the ensuing rich literature on sufficient LCP IPMs, the linear dependence on the handicap number has not been improved since then. We present an IPM whose running time depends on the square root of the handicap number. The algorithm can decrease the duality gap by a constant factor in O(min⁡{n(1+κ),n9/81+κ})O\left(\min\left\{\sqrt{n} (1+κ),n^{9/8}\sqrt{1+κ}\right\}\right) iterations. Curiously, this can already be achieved using standard Newton updates. We analyze the IPM in a norm defined by a local weighting, where centralizing Newton steps quadratically converge to the central path, without any dependence on the handicap number. The weights arise from a characterization by Rump (Linear Algebra and Its Applications, 1997, 1998, 2003) of the sign-real spectral radius and its relation to sufficiency; another ingredient of our proof is a new operator norm characterization of the handicap number. Moreover, the connection to Rump's work also enables us to show coNP-completeness of testing sufficiency, and approximation hardness of the handicap number.

Introduction

Interior point methods (IPMs) are among the most powerful algorithmic tools for continuous optimization. Their success is closely tied to convexity, which provides the structure needed to control Newton steps and guarantee rapid convergence. A longstanding question is how far these methods can be extended beyond convex optimization, and what properties can replace convexity in their convergence analysis.

An important setting for studying this question is the linear complementarity problem (LCP). Given a matrix M∈Rn×nM \in\mathbb{R}^{n \times n} and a vector q∈Rnq \in\mathbb{R}^n, the goal is to find vectors x,s∈Rnx,s \in\mathbb{R}^n satisfying

Mx+q=s,xTs=0,x,s≥0n.(1)Mx + q = s,\qquad x^\mathsf{T}s = 0,\qquad x,s \geq0_n. \tag*{(1)}

The LCP encompasses a remarkably broad range of problems. In particular, the optimality conditions of linear and convex quadratic programs can be expressed as LCPs, and complementarity formulations arise naturally in economic equilibria, noncooperative games, and variational inequalities. They were first studied in the 1960s by Lemke [41] and by Cottle and Dantzig [3], extending the complementary pivot algorithm by Lemke and Howson [42] from bimatrix games to the more general setting. We refer the reader to the books by Cottle, Pang, and Stone [8] and by Murty and Yu [52] for comprehensive treatments of LCP.

The best understood case is that of monotone LCPs, where M+MTM + M^\mathsf{T} is positive semidefinite, or equivalently, xTMx≥0x^\mathsf{T}Mx \geq0 for every x∈Rnx \in\mathbb{R}^n. Much like convex optimization problems, monotone LCPs can be solved in polynomial time by standard interior point methods (IPMs) [39, 15, 40, 86, 85]. Unfortunately, many important LCPs do not enjoy this structure. For unrestricted matrices, solving an LCP is NP-hard [5], and the complexity of several natural matrix classes remains a major open problem.

A particularly important example is the class of P\mathcal{P}-matrices, which are matrices whose principal minors are all positive. Every P\mathcal{P}-matrix MM has the property that LCP(M,q)(M,q) admits a unique solution for every qq, a fact established already before the explicit introduction of the LCP model [73]. Cottle and Dantzig [3] showed that Lemke’s algorithm finitely finds a solution for this class, yet there are still no polynomial time algorithms known. Megiddo [49] showed that solving PP-matrix LCP cannot be NP-hard unless NP=coNP. The significance of this problem extends well beyond mathematical optimization. PP-matrix LCPs are closely connected to unique sink orientations of hypercubes [74, 75] and to the complexity of total search problems: they are among the first problems shown to lie in PPAD by Papadimitriou [55], and also belong to the subclass UEOPL of PPAD [20]. Prominent problems at the intersection of automata theory and algorithmic game theory, such as discounted stochastic games, mean-payoff and parity games, admit reductions to PP-matrix LCPs [25, 34, 29, 20]. These connections make the search for efficient algorithms for structured LCPs an important direction in theoretical computer science and in optimization.

Analogously to their distinguished role in the context of pivoting algorithms, PP-matrix LCPs are also amenable to interior point methods. A seminal work by Kojima, Megiddo, Noma, and Yoshise [38] introduced the parametrized matrix class P⋆(κ)P_{\star}(\kappa), and gave an interior point method for P⋆(κ)P_{\star}(\kappa)-LCP with running time polynomial in the input and linear in κ\kappa. The parameter κ\kappa, known as the handicap number, measures the extent to which a matrix violates monotonicity; every PP-matrix belongs to P⋆(κ)P_{\star}(\kappa) for some κ≥0\kappa\ge0. However, this does not yield a polynomial-time algorithm for PP-matrix LCP, because κ\kappa can be exponentially large in the input encoding length.

This was followed by a long line of work on developing IPMs for P⋆(κ)P_{\star}(\kappa)-matrix LCPs, e.g., [50, 62, 63, 60, 56, 43, 64, 61, 44, 33, 18, 11], see also § 1.2. The literature explored a variety of IPMs using different neighborhoods, short and long-steps, as well as different kernel functions and reparametrizations. However, the best known running time bounds for P⋆(κ)P_{\star}(\kappa)-LCPs have retained a linear dependence on κ\kappa.

In this paper, we make the first improvement to this dependence in over three decades, showing that it can be reduced from linear to square root. Among extensive efforts to improve IPM iteration complexity across diverse regimes [47, 48 CMSV17, 45, 2, 37, 83, 46], to the extent of our knowledge this is the first result to break a longstanding bound by reanalyzing the classical method in a norm dictated by combinatorial structure.

Handicap number and LCPs for P⋆P_{\star}-matrices. To understand the handicap number, recall that monotonicity requires

xTMx=∑i=1nxi(Mx)i≥0,for all x∈Rn.x^{\mathsf{T}}Mx = \sum_{i=1}^{n} x_i(Mx)_i \ge0,\qquad\text{for all } x \in\mathbb{R}^{n}.

Although the individual terms in this sum may be negative, their total must be nonnegative. The defining property of P⋆(κ)P_{\star}(\kappa)-matrices relaxes this requirement by allowing the negative terms to outweigh the positive ones, provided that multiplying the positive contributions by 1+4κ1+4\kappa restores nonnegativity. Formally, for x∈Rnx \in\mathbb{R}^{n}, define the index sets according to the sign of xi(Mx)ix_i(Mx)_i:

IM+(x):={i∈[n]:xi(Mx)i>0},andIM−(x):={i∈[n]:xi(Mx)i<0}.\mathcal{I}^{+}_{M}(x) := \{i \in[n] : x_i(Mx)_i > 0\}, \qquad\text{and}\qquad\mathcal{I}^{-}_{M}(x) := \{i \in[n] : x_i(Mx)_i < 0\}.

The handicap number of MM is defined as

κ^(M):=inf⁡{κ≥0:(1+4κ)∑i∈IM+(x)xi(Mx)i+∑i∈IM−(x)xi(Mx)i≥0,∀x∈Rn}.(2)\widehat{\kappa}(M) := \inf\left\{ \kappa\ge0 : (1+4\kappa)\sum_{i\in\mathcal{I}^{+}_{M}(x)} x_i(Mx)_i + \sum_{i\in\mathcal{I}^{-}_{M}(x)} x_i(Mx)_i \ge0,\quad\forall x\in\mathbb{R}^{n} \right\}. \tag*{(2)}

We let P⋆(κ)P_{\star}(\kappa) denote the set of matrices with κ^(M)≤κ\widehat{\kappa}(M) \le\kappa, and write P⋆:=⋃κ≥0P⋆(κ)P_{\star} := \bigcup_{\kappa\ge0} P_{\star}(\kappa) for the class of matrices with finite handicap. Thus, P⋆(0)P_{\star}(0) is precisely the class of monotone matrices.

The class P⋆P_{\star} is of great significance within complementarity theory. A deep theorem by Väliaho [81] (Theorem 2.3) shows that it coincides with the class of sufficient matrices, originally introduced by Cottle, Pang, and Venkateswaran [9]. A matrix M∈Rn×nM \in\mathbb{R}^{n\times n} is column sufficient if for all x∈Rnx \in\mathbb{R}^{n}, x(Mx)≤0nx(Mx) \le0_n implies x(Mx)=0nx(Mx)=0_n, and row sufficient if MTM^{\mathsf{T}} is column sufficient; the product between xx and MxMx is applied entry-wise. A matrix is called sufficient if it is both column and row sufficient.

Moreover, P⋆P_{\star}-LCP appears to be the broadest class where one may hope for polynomial-time algorithms: let P0P_0 denote the class of matrices whose principal minors are all nonnegative; such matrices arise as limits of sequences of PP-matrices (see Lemma 2.4). Solving P0P_0-LCP is already NP-hard [38 Section 3.4]. Sufficient matrices fall strictly between these classes: P⊊P⋆⊊P0P \subsetneq P_{\star} \subsetneq P_0 [38 Section 3.2].

While the linear dependence on κ\kappa has not been improved in the extensive previous literature, there are compelling reasons to believe that this dependence is suboptimal. One particularly revealing example comes from discounted turn-based stochastic games, which can be encoded as P\mathcal{P}-matrix LCPs. Hansen and Ibsen-Jensen [29] showed that, for games with nn states and discount factor γ∈(0,1)\gamma\in(0,1), the corresponding matrices have handicap numbers being O(n(1−γ)2)O\left(\frac{n}{(1-\gamma)^2}\right), and gave an example where this bound is attained. Consequently, the classical handicap-based IPM bounds incur a quadratic dependence on 1/(1−γ)1/(1-\gamma). In contrast, specialized strategy-iteration algorithms for these games achieve a dependence that is linear in 1/(1−γ)1/(1-\gamma), up to logarithmic factors [31]; see further discussion in § 1.2.

This gap suggests that the handicap-based IPM analysis may be losing substantially more than necessary. The 1+κ\sqrt{1+\kappa} dependence in Theorem 1.2 below reduces the dependence on the inverse discount gap from quadratic to linear, matching the exponent achieved by specialized combinatorial algorithms; and thus provides a natural milestone for progress for IPM on P⋆(κ)\mathcal{P}_{\star}(\kappa)-LCPs. Our work may raise hopes towards log⁡(1+κ)\log(1+\kappa) dependence; this would imply a polynomial-time algorithm for P⋆\mathcal{P}_{\star}-LCP, and consequently for all these applications.

Our contributions

New characterization of P⋆(κ)\mathcal{P}_{\star}(\kappa)-matrices. Classical analyses of interior point methods for P⋆(κ)\mathcal{P}_{\star}(\kappa)-LCPs build directly on the definition in (1). Our equivalent characterization of κ^(M)\hat{\kappa}(M) is given in terms of a matrix norm that arises naturally in analyses of interior point methods. This result leads to simpler, more transparent proofs of known results, and is also a key ingredient in our improved analysis. For A∈Rm×nA \in\mathbb{R}^{m \times n}, we let ∥A∥2=∥A∥2→2=max⁡x∈Rn,∥x∥2=1∥Ax∥\|A\|_2 = \|A\|_{2 \to2} = \max_{x \in\mathbb{R}^n,\|x\|_2=1} \|Ax\| denote the spectral norm, i.e., the ℓ2→ℓ2\ell_2 \to\ell_2 operator norm. Let D>0n⊆Rn×n\mathcal{D}_{>0}^n \subseteq\mathbb{R}^{n \times n} denote the set of positive diagonal matrices.

Theorem 1.1. Let M∈Rn×nM \in\mathbb{R}^{n \times n}. Then, M∈P⋆M \in\mathcal{P}_{\star} if and only if In+DMDI_n + DMD is nonsingular for any D∈D>0nD \in\mathcal{D}_{>0}^n and sup⁡D∈D>0n∥(In+DMD)−1∥2\sup_{D \in\mathcal{D}_{>0}^n}\|(I_n + DMD)^{-1}\|_2 is finite. If M∈P⋆M \in\mathcal{P}_{\star}, then

sup⁡D∈D>0n∥(In+DMD)−1∥2=1+κ^(M)21/4+κ^(M).(3)\sup_{D \in\mathcal{D}_{>0}^n}\|(I_n + DMD)^{-1}\|_2 = \sqrt{1 + \frac{\hat{\kappa}(M)^2}{1/4 + \hat{\kappa}(M)}}. \tag*{(3)}

The proof is given in § 9.1. Besides being the key to our improved analysis, it also leads to simple new proofs of a theorem of Väliaho [82] showing that the handicap number is invariant under transposition, see Theorem 2.6.

Improved IPM analysis via algebraic and combinatorial properties. As we will see in Section 4, Newton steps for interior point methods involve matrix inverses of the form as in (2). In Theorem 4.2, we give a simple analysis showing that O(n(1+κ^(M))log⁡(ρ))O(\sqrt{n}(1+\hat{\kappa}(M))\log(\rho)) Newton steps suffice to reduce the optimality gap by a factor ρ\rho. Our main result improves the running time dependence to 1+κ^(M)\sqrt{1+\hat{\kappa}(M)}.

References

  1. [1]R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc., 1993.
  2. [2]K. Axiotis, A. Ma̧dry, and A. Vladu. Circulation control for faster minimum cost flow in unit-capacity graphs. In 61st Annual Symposium on Foundations of Computer Science, pages 93–104. IEEE, 2020.arxiv.org/abs/2003.04863
  3. [3]R. W. Cottle and G. B. Dantzig. Complementary pivot theory of mathematical programming. Linear Algebra and its Applications, 1(1):103–125, 1968.
  4. [4]R. W. Cottle and S.-M. Guu. Two characterizations of sufficient matrices. Linear Algebra and Its Applications, 170:65–74, 1992.
  5. [5]S.-J. Chung. NP-completeness of the linear complementarity problem. Journal of Optimization Theory and Applications, 60(3):393–399, 1989.DOI
  6. [8]R. W. Cottle, J.-S. Pang, and R. E. Stone. The linear complementarity problem. SIAM, 2009.
  7. [9]R. Cottle, J.-S. Pang, and V. Venkateswaran. Sufficient matrices and the linear complementarity problem. Linear Algebra and Its Applications, 114:231–249, 1989.DOI
  8. [10]Z. Darvay. New interior point algorithms in linear programming. Advanced Modeling and Optimization, 5(1):51–92, 2003.
  9. [11]Z. Darvay, M. E.-Nagy, G. Lesaja, P. R. Rigó, and A. Varga. Comprehensive analysis of kernel-based interior-point methods for the P*(κ)-LCP. SIAM Journal on Optimization, 36(2):887–911, 2026.
  10. [12]D. Dadush, S. Huiberts, B. Natura, and L. A. Végh. A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix. Mathematical Programming, 204:135–206, 2024. Preliminary version in STOC 2020.
  11. [13]Z. Darvay, T. Illés, J. Povh, and P. R. Rigó. Feasible corrector-predictor interior-point algorithm for P*(κ)-linear complementarity problems based on a new search direction. SIAM Journal on Optimization, 30(3):2628–2658, 2020.DOI
  12. [14]E. de Klerk and M. E.-Nagy. On the complexity of computing the handicap of a sufficient matrix. Mathematical Programming, 129(2):383–402, 2011.
  13. [15]J. Ding and T.-Y. Li. A polynomial-time predictor-corrector algorithm for a class of linear complementarity problems. SIAM Journal on Optimization, 1(1):83–92, 1991.DOI
  14. [16]M. E.-Nagy, T. Illés, Y. Nesterov, and P. R. Rigó. Parabolic target-space interior-point algorithm for monotone weighted linear complementarity problem. Mathematical Programming, pages 219(1):553–582, 2026.
  15. [17]M. E.-Nagy, T. Illés, J. Povh, A. Varga, and J. Žerovnik. Sufficient matrices: properties, generating and testing. Journal of Optimization Theory and Applications, 202(1):204–236, 2024.
  16. [18]M. E.-Nagy and A. Varga. A new Ai–Zhang type interior point algorithm for sufficient linear complementarity problems. Journal of Optimization Theory and Applications, 202(1):76–107, 2024.
  17. [19]M. E.-Nagy and L. A. Végh. Handicap reduction for linear complementarity problems. arXiv preprint arXiv:2605.10701, 2026.
  18. [20]J. Fearnley, S. Gordon, R. Mehta, and R. Savani. Unique end of potential line. Journal of Computer and System Sciences, 114:1–35, 2020.arxiv.org/abs/1811.03841
  19. [21]M. Fiedler and V. Pták. Cyclic products and an inequality for determinants. Czechoslovak Mathematical Journal, 19(3):428–450, 1969.DOI
  20. [22]K. Fukuda and T. Terlaky. Linear complementarity and oriented matroids. Journal of the Operations Research Society of Japan, 35(1):45–61, 1992.DOI
  21. [23]T. Gallai. Maximum-Minimum Sätze über Graphen. Acta Mathematica Academiae Scientiarum Hungaricae, 9(3–4):395–434, 1958.DOI
  22. [24]S.-M. Guu and R. W. Cottle. On a subclass of P₀. Linear Algebra and Its Applications, 223:325–335, 1995.DOI
  23. [25]B. Gärtner and L. Rüst. Simple stochastic games and P-matrix generalized linear complementarity problems. In International Symposium on Fundamentals of Computation Theory, pages 209–220. Springer, 2005.
  24. [26]M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6):1115–1145, 1995.DOI
  25. [27]N. Halman. Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems. Algorithmica, 49(1):37–50, 2007.DOI
  26. [28]J. Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798–859, 2001.
  27. [29]T. D. Hansen and R. Ibsen-Jensen. The complexity of interior point methods for solving discounted turn-based stochastic games. In Conference on Computability in Europe, pages 252–262. Springer, 2013.arxiv.org/abs/1304.1888
  28. [30]R. A. Horn and C. R. Johnson. Topics in Matrix Analysis. Cambridge University Press, Cambridge, 1991.DOI
  29. [31]T. D. Hansen, P. B. Miltersen, and U. Zwick. Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. Journal of the ACM (JACM), 60(1):1–16, 2013.arxiv.org/abs/1008.0530
  30. [32]T. Illés, M. Nagy, and T. Terlaky. EP theorem for dual linear complementarity problems. Journal of Optimization Theory and Applications, 140(2):233–238, 2009.DOI
  31. [33]T. Illés, M. Nagy, and T. Terlaky. A polynomial path-following interior point algorithm for general linear complementarity problems. Journal of Global Optimization, 47(3):329–342, 2010.
  32. [34]M. Jurdziński and R. Savani. A simple P-matrix linear complementarity problem for discounted games. In Conference on Computability in Europe, pages 283–293. Springer, 2008.DOI
  33. [35]L. Khachiyan. On the complexity of approximating extremal determinants in matrices. Journal of Complexity, 11(1):138–153, 1995.DOI
  34. [36]S. Khot, G. Kindler, E. Mossel, and R. O’Donnell. Optimal inapproximability results for max-cut and other 2-variable CSPs? SIAM Journal on Computing, 37(1):319–357, 2007.
  35. [37]T. Kathuria, Y. P. Liu, and A. Sidford. Unit capacity maxflow in almost O(m^{4/3}) time. In 61st Annual Symposium on Foundations of Computer Science, pages 119–130. IEEE, 2020.
  36. [38]M. Kojima, N. Megiddo, T. Noma, and A. Yoshise. A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, volume 538 of Lecture Notes in Computer Science. Springer, Berlin, 1991.
  37. [39]M. Kojima, S. Mizuno, and A. Yoshise. A polynomial-time algorithm for a class of linear complementarity problems. Mathematical Programming, 44(1):1–26, 1989.
  38. [40]M. Kojima, N. Megiddo, and Y. Ye. An interior point potential reduction algorithm for the linear complementarity problem. Mathematical Programming, 54(1–3):267–279, 1992.DOI
  39. [41]C. E. Lemke. Bimatrix equilibrium points and mathematical programming. Management Science, 11(7):681–689, 1965.DOI
  40. [42]C. E. Lemke and J. T. Howson, Jr. Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2):413–423, 1964.
  41. [43]X. Liu and F. A. Potra. Corrector-predictor methods for sufficient linear complementarity problems in a wide neighborhood of the central path. SIAM Journal on Optimization, 17(3):871–890, 2006.
  42. [44]G. Lesaja and C. Roos. Unified analysis of kernel-based interior-point methods for P∗(κ)-linear complementarity problems. SIAM Journal on Optimization, 20(6):3014–3039, 2010.DOI
  43. [45]Y. P. Liu and A. Sidford. Faster energy maximization for faster maximum flow. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020.arxiv.org/abs/1910.14276
  44. [46]C.-H. Liu, A. Sidford, and T.-W. Tu. Near-optimal parallel M-matrix scaling. arXiv preprint arXiv:2610.22302, 2026.arxiv.org/abs/2610.22302
  45. [47]A. Madry. Navigating central path with electrical flows: From flows to matchings, and back. In 54th Annual Symposium on Foundations of Computer Science, pages 253–262. IEEE, 2013.arxiv.org/abs/1307.2205
  46. [48]A. Madry. Computing maximum flow with augmenting electrical flows. In 57th Annual Symposium on Foundations of Computer Science, pages 593–602. IEEE, 2016.arxiv.org/abs/1608.06016
  47. [49]N. Megiddo. A note on the complexity of P-matrix LCP and computing an equilibrium. Research Report RJ 6439, IBM Almaden Research Center, San Jose, CA, 1988.
  48. [50]J. Miao. A quadratically convergent O((κ + 1)√nL)-iteration algorithm for the P∗(κ)-matrix linear complementarity problem. Mathematical Programming, 69(1):355–368, 1995.DOI
  49. [51]S. Mizuno, M. J. Todd, and Y. Ye. On adaptive-step primal-dual interior-point algorithms for linear programming. Mathematics of Operations Research, 18(4):964–981, 1993.
  50. [52]K. G. Murty and F.-T. Yu. Linear complementarity, linear and nonlinear programming, volume 3. Heldermann, Berlin, 1988.
  51. [53]OpenAI. Turn-based stochastic mean-payoff games in deterministic quasipolynomial time. AI-generated manuscript, family 104 (“Quasipolynomial algorithms for mean-payoff, stochastic and parity games”) in the openai/math repository, October 2026. Dated October 5, 2026; released October 6, 2026 (collection version adc7f12). Accessed November 1, 2026.hub.valency.io/works/W_67kw35ma
  52. [54]OpenAI. The unique games theorem. AI-generated manuscript, family 102 (“The Unique Games Conjecture and optimal approximation thresholds”) in the openai/math repository, September 2026. Dated September 23, 2026; released October 6, 2026. Accessed October 27, 2026.hub.valency.io/works/W_xra45zpr
  53. [55]C. H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498–532, 1994.DOI
  54. [56]F. A. Potra and X. Liu. Predictor-corrector methods for sufficient linear complementarity problems in a wide neighborhood of the central path. Optimization Methods and Software, 20(1):145–168, 2005.
  55. [57]F. A. Potra. Weighted complementarity problems—a new paradigm for computing equilibria. SIAM Journal on Optimization, 22(4):1634–1654, 2012.DOI
  56. [58]F. A. Potra. Sufficient weighted complementarity problems. Computational Optimization and Applications, 64(2):467–488, 2016.DOI
  57. [59]S. Poljak and J. Rohn. Checking robust nonsingularity is NP-hard. Mathematics of Control, Signals and Systems, 6(1):1–9, 1993.DOI
  58. [60]J. Peng, C. Roos, and T. Terlaky. New complexity analysis of primal-dual Newton methods for P∗(κ) linear complementarity problems. In High Performance Optimization, pages 245–265. Springer, 2000.DOI
  59. [61]J. Peng, C. Roos, and T. Terlaky. Self-regularity: a new paradigm for primal-dual interior-point algorithms. Princeton University Press, 2009.
  60. [62]F. A. Potra and R. Sheng. Predictor-corrector algorithm for solving P_*(κ)-matrix LCP from arbitrary positive starting points. Mathematical Programming, 76:223–244, 1996.
  61. [63]F. A. Potra and R. Sheng. A large-step infeasible-interior-point method for the P_*-matrix LCP. SIAM Journal on Optimization, 7(2):318–335, 1997.DOI
  62. [64]F. A. Potra and J. Stoer. On a class of superlinearly convergent polynomial time interior point methods for sufficient LCP. SIAM Journal on Optimization, 20(3):1333–1363, 2009.DOI
  63. [65]A. P. Punnen. The quadratic unconstrained binary optimization problem. Springer, 2022.DOI
  64. [66]S. M. Rump. Theorems of Perron–Frobenius type for matrices without sign restrictions. Linear Algebra and Its Applications, 266:1–42, 1997.DOI
  65. [67]S. M. Rump. The sign-real spectral radius and cycle products. Linear Algebra and Its Applications, 279(1-3):177–180, 1998.DOI
  66. [68]S. M. Rump. On P-matrices. Linear Algebra and Its Applications, 363:237–250, 2003.
  67. [69]S. M. Rump. Perron–Frobenius theory for complex matrices. Linear Algebra and Its Applications, 363:251–273, 2003.DOI
  68. [70]A. Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1998.
  69. [71]A. Soleymani and G. Farina. A quasipolynomial algorithm for ℓ∞ contractions. arXiv preprint arXiv:2610.30122, 2026.arxiv.org/abs/2610.30122
  70. [72]L. S. Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 39(10):1095–1100, 1953.
  71. [73]H. Samelson, R. M. Thrall, and O. Wesler. A partition theorem for Euclidean n-space. Proceedings of the American Mathematical Society, 9(5):805–807, 1958.DOI
  72. [74]A. Stickney and L. Watson. Digraph models of Bard-type algorithms for the linear complementarity problem. Mathematics of Operations Research, 3(4):322–333, 1978.DOI
  73. [75]T. Szabó and E. Welzl. Unique sink orientations of cubes. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 547–555. IEEE, 2001.DOI
  74. [76]K. Truemper. On max flows with gains and pure min-cost flows. SIAM Journal on Applied Mathematics, 32(2):450–456, 1977.DOI
  75. [77]P. Tseng. Co-NP-completeness of some matrix classification problems. Mathematical Programming, 88(1):183–192, 2000.DOI
  76. [78]L. Trevisan, G. B. Sorkin, M. Sudan, and D. P. Williamson. Gadgets, approximation, and linear programming. SIAM Journal on Computing, 29(6):2074–2097, 2000.
  77. [79]L. Tunçel. Approximating the complexity measure of Vavasis–Ye algorithm is NP-hard. Mathematical Programming, 86(1):219–223, 1999.DOI
  78. [80]H. Väliaho. Criteria for sufficient matrices. Linear Algebra and Its Applications, 233:109–129, 1996.DOI
  79. [81]H. Väliaho. P_*-matrices are just sufficient. Linear Algebra and Its Applications, 239:103–108, 1996.DOI
  80. [82]H. Väliaho. Determining the handicap of a sufficient matrix. Linear Algebra and Its Applications, 253(1-3):279–298, 1997.DOI
  81. [83]A. Vladu. Breaking the barrier of self-concordant barriers: Faster interior point methods for M-matrices. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 2213–2224, 2025.arxiv.org/abs/2504.20619
  82. [84]S. A. Vavasis and Y. Ye. A primal-dual interior point method whose running time depends only on the constraint matrix. Mathematical Programming, 74(1):79–120, 1996.DOI
  83. [85]S. J. Wright. Primal-dual interior-point methods. SIAM, 1997.
  84. [86]Y. Ye and K. Anstreicher. On quadratic and O(√nL) convergence of a predictor-corrector algorithm for LCP. Mathematical Programming, 62(1):537–551, 1993.
  85. [87]U. Zwick and M. Paterson. The complexity of mean payoff games on graphs. Theoretical Computer Science, 158(1-2):343–359, 1996.DOI
  86. [88]U. Zwick. Improved subexponential analysis of the random-action-removal algorithm for 2-player turn-based games and non-binary AUSOs. arXiv preprint arXiv:2607.06334, 2026.arxiv.org/abs/2607.06334

Paper details

vlnc:W_gnvqqe9n
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT, DeepSeek, LLM

View statement
Looking for related papers…
Contents