Streaming Weighted Set Cover Requires (Nearly) Linear SpaceResearch Paper
In streaming set cover, sets over an -element universe arrive one at a time; an algorithm makes a few passes with limited memory and must approximate the minimum total weight of a cover. Storing the input costs bits, the incidence matrix. Running time is unrestricted, so the question is purely about information: how much memory a given number…