On the non-polynomiality of the relaxation method for systems of linear inequalities |
| |
| Authors: | J L Goffin |
| |
| Institution: | (1) Faculty of Management, McGill University, Montreal, Quebec, Canada |
| |
| Abstract: | A class of linear programs is given in which the relaxation method for inequalities, under the same operating rules as Khacian's method, is not polynomial in the length of the input. This result holds for any value of the relaxation parameter.This research was supported in part by the D.G.E.S. (Quebec), the N.S.E.R.C. of Canada under grant A 4152, and the S.S.H.R.C. of Canada. |
| |
| Keywords: | Linear Programming Relaxation Method Polynomiality |
| 本文献已被 SpringerLink 等数据库收录！ |
|
