独立集上最小最大比值和最小极差比值问题的算法

The algorithms for the max-min and minimal extreme difference ratio problems on an independent system

定义在集Ｅ的子集Ｘ上的两个实函数的比值的极大、极小值分别记为Ｍ（Ｘ）和ｍ（Ｘ），极差△（Ｘ）＝Ｍ（Ｘ）－ｍ（Ｘ）。本文给出在秩为ｒ的独立系统（Ｅ，Ｉ）（ＩＰ（Ｅ））中求ｍａｘ｛ｍ（Ｘ）｜Ｘ∈Ｉ｜，｜Ｘ｜＝ｒ｝和ｍｉｎ｛△（Ｘ）｜Ｘ∈Ｉ｜，｜Ｘ｜＝ｒ｝的有效算法及其证明。

Let E be a set, λ(x) be the radio value of two real functions defined on XE,M(X) =max {λ(x)|x∈X}, m(X)=min {λ(x)|x∈X}. We call △ (X)=M(X)-m(x)the extreme difference of X. Let (E,I) be an independent system with rank r. The algorithms are given for finding the max {m(X)|X∈I,|X|=r} and the min{△(X)|X∈I, |X|=r}.