Accession Number : AD0622609
Title : COVERING PROBLEMS: DUALITY RELATIONS AND A NEW METHOD OF SOLUTION.
Descriptive Note : Technical rept.,
Corporate Author : INFORMATION SYSTEMS LAB UNIV OF MICHIGAN ANN ARBOR
Personal Author(s) : Lawler,Eugene L.
Report Date : MAY 1965
Pagination or Media Count : 33
Abstract : This paper is concerned with 'covering' problems of the following type: Let a strictly positive n-vector c and an mxn matrix A of O's and 1's be given. Let epsilon = (1,1,...,1) be an m-vector of 1's. Find a solution vector y = (y1,y2,...,yn) which will minimize the inner product cy subject to Ay > or = epsilon and y sub j = O or 1 (j=1,2,...,n). There is an interesting duality between the constraints of covering problems and their solutions. This duality is explored in this paper and is found to furnish the basis for a possible new method of solution which is described in detail. (Author)
Descriptors : (*LINEAR PROGRAMMING, OPTIMIZATION), MATRICES(MATHEMATICS), COMBINATORIAL ANALYSIS, VECTOR ANALYSIS, OPERATIONS RESEARCH, SET THEORY
Distribution Statement : APPROVED FOR PUBLIC RELEASE