求解单位L_(∞)范数下带值约束的最大权完美匹配逆问题的算法  

Algorithm for Solving the Inverse Problem of Maximum Weight Perfect Matching with Value Constraints under Unit L_(∞)Norm

作　　者：周泽聿 于成成 张斌武[2] ZHOU Ze-yu;YU Cheng-cheng;ZHANG Bin-wu(Business School,Hohai University,Changzhou 213022,China;School of Mathematics,Hohai University,Nanjing 210098,China)

机构地区：[1]河海大学商学院,江苏常州213022 [2]河海大学数学学院,江苏南京210098

出　　处：《数学的实践与认识》2023年第11期114-119,共6页Mathematics in Practice and Theory

基　　金：国家自然科学基金(11471073);中央高校业务费(2018B44014);国家级大学生创新创业训练项目(201810294084)。

摘　　要：通过研究单位L_(∞)范数下的带值约束的最大权完美匹配逆问题的性质,将单位L_(∞)范数下最大权完美匹配逆问题转化为求解最大平均交替圈问题,给出一个求解该类问题的一个强多项式时间算法,其时间复杂度为O(n^(4)).并通过一个算例,验证了给出的算法的有效性.By studying the properties of the inverse problem of the maximum weight perfect matching with the value constraint under the unit L_(∞)norm,the inverse problem of the maximum weight perfect matching under the unit L_(∞)norm is transformed into the maximum average alternating circle problem,and a strong polynomial time algorithm with running time O(n^(4))to the problem is given.The validity and correctness of the proposed algorithm are verified by an example.

关 键 词：最大权完美匹配 单位L_(∞)范数 强多项式时间 值约束 

分 类 号：O157.5[理学—数学]