A Structure-Tensor Approach to Integer Matrix Completion in Indivisible Resource Allocation

Indivisible resource allocation motivates us to study the matrix completion concerning the class of (0,1)-matrices with prescribed row/column sums and preassigned zeros. We illustrate and generalize the (0,1)-matrix completion in two scenarios: a demand-response application involving nonnegative integer matrices with different bounds across rows and an edge caching matching problem allowing row and column sums to vary within separately designated bounds. The applications require analytic characterizations of the supply adequacy and cause large-scale matrix completion instances. Remarkably, we derive a structure tensor and use its nonnegativity to establish a necessary and sufficient condition under which the considered matrix class is nonempty. The tensor condition can characterize the adequacy of a supply for a prescribed demand and facilitate identifying the minimum supplement to the supply so that the augmented supply becomes adequate when the adequacy gap is nonzero. Notably, we design a tensor-based combinatorial algorithm to construct a required matrix, representing a feasible resource allocation. Numerical simulations justify the efficiency of our approach.