Min-max partitioning problem with matroid constraint

In this paper, we consider the set partitioning problem with matroid constraint, which is a generation of the k-partitioning problem. The objective is to minimize the weight of the heaviest subset. We present an approximation algorithm, which consists of two sub-algorithms-the modified Edmonds' matroid partitioning algorithm and the exchange algorithm, for the problem. An estimation of the worst ratio for the algorithm is given.

等密拟阵在图论中的一个应用

研究等密拟阵在图论中的一个应用。由τc(G)的表示式,讨论了F∈β〔M′〔n-c〕〕的等价条件。证明了η〔M′〔n-c〕〕=τc(G)。结合等密拟阵的定义推得(ⅰ)τc(G)≥k的充要条件;(ⅱ)τc(G)=s等价条件;(ⅲ)当c=1时τc(G)的图论意义。