前提说明与定义

令 R 和 R^+ 分别表示实数集和非负实数集。给定一个全集 V = ，研究的问题是在 V 的子集上的函数 f : 2^V R。如果 X Y 时 f(X) ≤ f(Y)，则称集合函数 f 是单调的，这说明往一个集合添加更多元素时永远不会导致函数值减少。不失一般性地，假设，这些单调函数是归一化的，即 f( ) = 0。如果对于任意 X Y V 和 v Y，有 f(X∪) f(X)≥f(Y∪) f(Y)，则称集合函数 f 是子模 (submodular) 函数，这表示该函数具有增益递减性质，即向集合 X 增加元素时所带来的收益大于向 X 的超集 Y 添加同样的元素。

对于一个广义的集合函数 f，如定义 1 所示的子模比（submodularity）的概念可用于度量 f 所具有的子模性的程度。当 f 单调时，有这两个结论：（1）0 ≤ α_f ≤ 1；（2）α_f = 1 当且仅当 f 是子模函数。注意，在衡量 f 与子模性的相近程度方面还存在其它一些符号，比如 Krause and Cevher 2010; Das and Kempe 2011; Zhou and Spanos 2016 等中使用的符号。

定义 1：子模比。非负集合函数 f 的子模比定义为：

定义 2 所代表的总曲率描述了单调子模函数 f 与模块度（modularity）的相近程度。很容易验证 1 ≥ 1 – κ_f ≥ 0。在这篇论文中，研究者用κ_f 表示广义 单调函数。根据式（2），如果没有子模性，则 1/α_f ≥ 1 – κ_f ≥ 0 成立。

定义 2：总曲率。定义单调子模集合函数 f 的总曲率为：

定义 3 给出了本研究所关注的问题，即最大化单调目标 f，使得单调成本函数 c 的上界处在预算 B 的约束下。f 和 c 并不必须都是子模函数。假设 f 由一个 value oracle 给定，即对于任意子集 X，都有一个算法可以查询 oracle 以得到 f(X) 的值。和之前一些论文一样，研究者也假设精确的成本函数 c 是无法得到的，而只能得到一个 ψ(n) 近似 c ，其中 X V : c(X) ≤ c (X) ≤ ψ(n) · c(X)。这是因为在某些现实应用中，精确计算 c 所需的时间可能呈指数增长。

定义 3：文本所研究的广义问题。给定一个单调目标函数 f : 2^V R^+、一个单调成本函数 c : 2^V R^+ 以及预算 B，目标是找到：

这篇论文在三种应用上通过实验研究了单调子模目标函数。

第一种应用是最大覆盖问题。给定一组覆盖了元素全域的集合，最大覆盖任务的目标是在一定成本预算下选择出某些集合并使得这些集合的并集是最大的。可以很容易验证：f 是单调的子模函数。

定义 4：最大覆盖。给定一个元素集合 U、U 的一组子集 V =、一个单调成本函数 c : 2^V R^+ 以及预算 B，目标是找到：

第二种应用是影响力最大化，其目标是识别社交网络中有影响力的用户集。首先定义一个有向图 G = (V, E) 来表示社交网络，其中每个节点都是一个用户，每条边 (u, v) ∈ E（带有概率 p_）表示用户 u 到 v 的影响力强度。给定预算 B，影响力最大化的目标是找到 V 的一个子集 X，使得由源自 X 的传播而激活的节点的预期数量最大。独立级联（Independence Cascade/IC）是一种基础的传播模型。其使用一个集合 A_t 来记录在时间 t 激活的节点；在时间 t+1，u ∈ A_t 的每个未激活的邻近节点 v 都有 p_ 的概率被激活。这个过程不断重复，直到到达没有节点再被激活的时间。将由 X 的传播而激活的节点集记为 IC(X)，这是一个随机变量。目标 E[|IC(X)|] 被称为影响力传播度（influence spread），这是一个单调子模函数，其中 E[·] 是指随机变量的期望。

定义 5：影响力最大化。给定一个有向图 G = (V, E)，对于 (u, v)∈E，边概率为 p_；以及单调成本函数 c : 2^V R^+ 和预算 B，目标是找到：

第三个应用是传感器放置，其目标是决定有限数量的传感器的放置位置，使得不确定度能最大限度地降低。令 o_j 表示一个随机变量，其代表通过在位置 v_j 安装传感器而收集到的观察数据。注意，对于已经观察到子集 S 的随机变量的总集合 U，其条件熵（即剩余的不确定度）为 H(U | S) = H(U) H(S)，其中 H(·) 表示熵。因此，这个任务的目标是选择一个位置子集 X，使得 的熵最大。已知熵 H(·) 是一个单调子模函数。

定义 6：传感器放置。给定 n 个位置 V = 、单调成本函数 c : 2^V R^+ 和预算 B，目标是找到：

对于这些应用，成本限制可能是简单的规模限制，即 c(X) = |X|；或一般的线性成本限制，即

。但在某些情况中，这个限制可能更加复杂，比如路径限制，这是单调非子模的。举个例子，在移动机器人传感领域，需要计入在不同位置之间移动的成本以及在这些位置进行测量的成本。用图 G = (V, E) 表示所有位置的路径网络，其中 c_e 表示穿过一条边 e ∈ E 的成本，c_v 表示访问一个节点 v ∈ V 的成本。成本函数为

，其中是访问 X 中每个节点至少一次的最短行走的成本，这通常是非子模的，而且无法在多项式时间中得到准确的计算。本文的实验中，线性约束和路由约束都会用到。