(15 pts) Give a polynomial time algorithm for solving the following problem in matrices. Let U...

Transcribed Image Text:

(15 pts) Give a polynomial time algorithm for solving the following problem in matrices. Let U = (uij) be a fixed nn matrix with nonnegative integer entries. Let r1, r2, ..., rn, C1, C2 . . . Cn be 2n positive integers. Determine if there exists a nn matrix A = (aj) with nonnegative, integer entries such that all of the following hold: (i) For each i = , 1, n, the sum of the entries of row i is at most ri. (ii) For each j = 1,...,n, the sum of the entries in column j is exactly c;. (iii) A U, i.e., aij uij for each i, j = {1, ..., n} . Justify the correctness and the polynomial running time of your algorithm. (15 pts) Give a polynomial time algorithm for solving the following problem in matrices. Let U = (uij) be a fixed nn matrix with nonnegative integer entries. Let r1, r2, ..., rn, C1, C2 . . . Cn be 2n positive integers. Determine if there exists a nn matrix A = (aj) with nonnegative, integer entries such that all of the following hold: (i) For each i = , 1, n, the sum of the entries of row i is at most ri. (ii) For each j = 1,...,n, the sum of the entries in column j is exactly c;. (iii) A U, i.e., aij uij for each i, j = {1, ..., n} . Justify the correctness and the polynomial running time of your algorithm.