Abstract: The simple greedy algorithm for set multicover has approximation ratio. This paper presents a variation of the simple greedy algorithm, Breadth First Greedy Algorithm, and proves its approximation ratio can be （ln n）/r＋ lnlnn＋O（1）, where r is the cover re

Key words: Set multicover, Breadth first greedy algorithm, Multiplicative weights update method