COVERING PROBLEMS: DUALITY RELATIONS AND A NEW METHOD OF SOLUTION.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1965
- Accession Number
- AD0622609
Entities
People
- Eugene L. Lawler