On Submodular Search and Machine Scheduling

Robbert Fokkink, Thomas Lidbetter, László A. Végh

Suppose some objects are hidden in a finite set $S$ of hiding places which must be examined one-by-one. The cost of searching subsets of $S$ is given by a submodular function and t…