ABSTRACT

In this chapter, we study fundamental results on maximizing a special class of functions called submodular functions under various combinatorial constraints. The study of submodular functions is motivated both by their many real-world applications and by their frequent occurrence in more theoretical fields, such as economy and algorithmic game theory. In particular, submodular functions and submodular maximization play a major role in combinatorial optimization as several well-known combinatorial functions turn out to be submodular. A few examples of such functions include cuts functions of graphs and hypergraphs, rank functions of matroids and covering functions. We discuss some of these examples further in the following.