A neural algorithm for computing bipartite matchings

• 成果类型: Article
• 署名作者: Dasgupta, Sanjoy; Meirovitch, Yaron; Zheng, Xingyu; Bush, Inle; Lichtman, Jeff W.; Navlakha, Saket
• 署名单位: University of California System; University of California San Diego; Harvard University; Harvard University; Cold Spring Harbor Laboratory
• 刊物名称: PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA
• ISSN/ISSBN: 0027-9291
• DOI: 10.1073/pnas.2321032121
• 发表日期: 2024-09-10
• 关键词: motor unit size; synapse elimination; muscle; COMPETITION; connections; innervation; PRINCIPLE; neurons; cells; envy

摘要

Finding optimal bipartite matchings-e.g., matching medical students to hospitals for residency, items to buyers in an auction, or papers to reviewers for peer review-is a fundamental combinatorial optimization problem. We found a distributed algorithm for computing matchings by studying the development of the neuromuscular circuit. The neuromuscular circuit can be viewed as a bipartite graph formed between motor neurons and muscle fibers. In newborn animals, neurons and fibers are densely connected, but after development, each fiber is typically matched (i.e., connected) to exactly one neuron. We cast this synaptic pruning process as a distributed matching (or assignment) algorithm, where motor neurons compete with each other to win muscle fibers. We show that this algorithm is simple to implement, theoretically sound, and effective in practice when evaluated on real-world bipartite matching problems. Thus, insights from the development of neural circuits can inform the design of algorithms for fundamental computational problems.