论文部分内容阅读
在一个局部逆拟阵问题中,给定一个拟阵M=(S,I),S上的一个权重函数w,以及一个属于I的独立集I0,尽量少地将权重w改变到一个新的权重w使得存在一个包含I0的w-最大基.在本文中,我们研究了一个权重只允许增加(定义为CPIM+)或只允许减少(定义为CPIM?)的限制性的局部逆拟阵问题.当权重的改变在任何的单调不减的范数下,对于CPIM+我们提出了两个多项式时间算法,当权重的改变在l∞范数下,对于CPIM?我们提出了一个多项式时间算法.