If u does not have a neighbor in S, then u is added to S. By calculation, if u is chosen randomly from the remaining vertices, the expected increase in the pessimistic estimator is non-negative.
Если u не имеет соседей в множестве S, то u добавляется в S. Если u выбирается случайно из оставшихся вершин, ожидаемый рост пессимистического оценщика неотрицателен.