Strongly polynomial algorithm for a class of combinatorial LCPs

DOI10.1016/0167-6377(87)90036-8MaRDI QIDQ1088911zbMATH OpenOpenAlexFDO

Authors R. Chandrasekaran, Santosh N. Kabadi

Publication date 1987

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(87)90036-8

zbMATH Keywords

strongly polynomial algorithmlinear complementary problemconvex curve fittingfitting the best convex curve

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Recommendations

• A polynomial-time algorithm for a class of linear complementarity problems
• Some LCPs solvable in strongly polynomial time with Lemke's algorithm
• AN O(n^3L) ALGORITHM USING A SEQUENCE FOR A LINEAR COMPLEMENTARITY PROBLEM
• Polynomial interior point algorithms for general linear complementarity problems
• An interior point potential reduction algorithm for the linear complementarity problem

Cites work

• scientific article; zbMATH DE number 3850827 (Why is no real title available?)
• scientific article; zbMATH DE number 192986 (Why is no real title available?)
• Factoring polynomials with rational coefficients

Cited in

(5)

• On polynomial solvability of the high multiplicity total weighted tardiness problem
• Some LCPs solvable in strongly polynomial time with Lemke's algorithm
• A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks
• Two counterexamples on the polynomial solvability of the linear complementarity problem
• A polynomial algorithm for an integer quadratic non-separable transportation problem

This page was built for publication: Strongly polynomial algorithm for a class of combinatorial LCPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1088911)