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

convex curve fittingfitting the best convex curvelinear complementary problemstrongly polynomial algorithm

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)

Review text

We show that an LCP with positive definite coefficient matrix can be solved in time polynomially bounded by the size of the numbers in the coefficient matrix. As a special case, we have a strongly polynomial algorithm for the problem of fitting the best convex curve to a given set of points in \(R^ 2\).

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

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

Cited in

(5)

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