Finding Hall Blockers by Matrix Scaling

• 成果类型: Article
• 署名作者: Hayashi, Koyo; Hirai, Hiroshi; Sakabe, Keiya
• 署名单位: University of Tokyo; Nagoya University; University of Tokyo
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.0198
• 发表日期: 2024
• 页码: 2166-2179
• 关键词: algorithm

摘要

Given a nonnegative matrix A=(A(ij))=, the matrix scaling problem asks whether A can be scaled to a doubly stochastic matrix D1AD2 for some positive diagonal matrices D-1, D-2. The Sinkhorn algorithm is a simple iterative algorithm, which repeats row-normalization A(ij )<- A(ij)/& sum;(i)A(ij) and column-normalization A(ij )<- A(ij)/& sum;(i)A(ij) alternatively. By this algorithm, A converges to a doubly stochastic matrix in limit if and only if the bipartite graph associated with A has a perfect matching. This property can decide the existence of a perfect matching in a given bipartite graph G, which is identified with the 0, 1-matrix A(G). Linial et al. (2000) showed that O(n2log n) iterations for A(G) decide whether G has a perfect matching. Here, n is the number of vertices in one of the color classes of G. In this paper, we show an extension of this result. If G has no perfect matching, then a polynomial number of the Sinkhorn iterations identifies a Hall blocker-a vertex subset X having neighbors Gamma(X) with |X|>|Gamma(X)|, which is a certificate of the nonexistence of a perfect matching. Specifically, we show that O(n(2)log n) iterations can identify one Hall blocker and that further polynomial iterations can also identify all parametric Hall blockers X of maximizing (1-lambda)|X|-lambda|Gamma(X)| for lambda is an element of[0,1]. The former result is based on an interpretation of the Sinkhorn algorithm as alternating minimization for geometric programming. The latter is on an interpretation as alternating minimization for Kullback-Leibler (KL) divergence and on its limiting behavior for a nonscalable matrix. We also relate the Sinkhorn limit with parametric network flow, principal partition of polymatroids, and the Dulmage-Mendelsohn decomposition of a bipartite graph.