Strongly polynomial algorithm for a class of combinatorial LCPs
type: Item
instance of: scholarly article
title: Strongly polynomial algorithm for a class of combinatorial LCPs
zbMATH Open document ID: 0617.90079
DOI: 10.1016/0167-6377(87)90036-8
author: R. Chandrasekaran
author: Santosh N. Kabadi
published in: Operations Research Letters
publication date: 1987-01-01T00:00:00Z
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\).
Mathematics Subject Classification ID: 90C33
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4001886
zbMATH Keywords: linear complementary problem
zbMATH Keywords: convex curve fitting
zbMATH Keywords: strongly polynomial algorithm
zbMATH Keywords: fitting the best convex curve
MaRDI profile type: Publication
full work available at URL: 0167-6377(87)90036-8
OpenAlex ID: W2076336245
cites work: Q3320129
cites work: Factoring polynomials with rational coefficients
cites work: Q4039868
description: scientific article; zbMATH DE number 4001886