Submodular Functions Maximization Problems
Submodular Functions Maximization Problems
复制标题
DOI：
10.1201/9781351236423-42
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Niv Buchbinder;Moran Feldman
中科院分区：
文献类型：
--
作者：
Niv Buchbinder;Moran Feldman
在本章中，我们研究了在各种组合限制下的基本结果，称为supply函数，这既是由它们的许多现实世界应用以及它们在经济上经常出现的，例如经济性和算法的最大作用。良好的组合功能是削减图形的示例，包括图形和覆盖功能的等级a元素的元素。
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. Let us begin by providing basic notation used throughout the chapter. We then give two definitions of submodular functions and prove that they are equivalent. Let N = {u1, u2, . . . , un} be a ground set of elements. For a set A and an element u ∈ N we denote the union A ∪ {u} by A+ u. Similarly, we denote A \ {u} as A− u. The following is the first definition of submodular functions.