Set covering with our eyes closed