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

• 成果类型: Article
• 署名作者: Mo, Yanfang; Chen, Wei; Khong, Sei Zhen; Qiu, Li
• 署名单位: City University of Hong Kong; Peking University; Peking University; Hong Kong University of Science & Technology
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3161876
• 发表日期: 2022
• 页码: 4541-4554
• 关键词: Tensors; resource management; Upper bound; Parallel processing; Load management; indexes; CONTROLLABILITY; energy systems; indivisible resource allocation; integer matrix completion; Majorization; network flows

摘要

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 the following 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.