Homework 18

Due Monday, April 20 at 7:00 PM. Please refer to the homework policy here.

Problems

  1. Prove that max coverage is NP-Hard.

  2. Let be a fixed set of "ground elements" and let be a set function. is said to be:

    • nonnegative if for all .
    • monotonic if for all .
    • submodular if for any , and any , . (Here is a shorthand for .)

    Prove that the coverage function from the lecture, which takes a collection of sets and outputs the size of their union, is a nonnegative, monotonic, submodular function.

  3. Let be a monotone submodular function. Show that for any two sets and ,

  4. Let be a monotone submodular function, and let . Consider the following constrained maximization problem.

    As a generalization of maximum coverage, submodular maximization is also NP-Hard. Design and analyze an algorithm that obtains a -approximation for this problem.

Submodularity can be interpretted as a set function with decreasing marginal returns: the marginal value of adding an element to a set diminishes as is increasing. This is a very natural property that arises very naturally. Coverage and submodularity models many scenarios in combinatioral optimization, machine learning, game theory, and data mining, among others. For example, welfare maximization in problems in game theory are cast as submodular maximization, because the utilities of agents tends to be submodular. Feature selection im machine learning is sometimes modeled as submodular maximization, in the sense that each additional feature we add to the model may have some "overlapping information" with previously selecting information. (These arguments are made very precise in real settings.) So what we have really done is come up with an approximation algorithm for a very broad class of problems.