图 书 馆
多拟阵与子模性Polymatroids and Submodularity |
|
| 课程网址: | http://videolectures.net/nipsworkshops2011_edmonds_polymatroids/ |
| 主讲教师: | Jack Edmonds |
| 开课单位: | 无 |
| 开课时间: | 2012-01-25 |
| 课程语种: | 英语 |
| 中文简介: |  现在已经提出了许多折时算法，用于最小化有限集E的子集S上的子模函数f（S）。我们提供了（全部隐藏的）所有理论基础的教程。特别是，可以很容易地将f推算为一个子函数，不递减且在空集合上为零的集合函数g（S），因此最小化f（S）等同于重复确定点x是否在多拟阵中。 ，P（g）= {x：x> = 0，并且对于每个S，S中j上的x（j）之和最多为g（S）}。一个基本定理说，假设g（S）是整数，则P（g）中的0,1向量x是拟阵M（P（g））的独立集合的入射向量。另一个给出了P（g）顶点的简单描述。我们将展示这些想法如何为可能有用的最佳分支系统问题提供漂亮但复杂的多时算法。 |
| 课程简介: | Many polytime algorithms have now been presented for minimizing a submodular function f(S) over the subsets S of a finite set E. We provide a tutorial in (somewhat hidden) theoretical foundations of them all. In particular, f can be easily massaged to a set function g(S) which is submodular, non-decreasing, and zero on the empty set, so that minimizing f(S) is equivalent to repeatedly determining whether a point x is in the polymatroid, P(g) = {x : x >= 0 and, for every S, sum of x(j) over j in S is at most g(S)}. A fundamental theorem says that, assuming g(S) is integer, the 0,1 vectors x in P(g) are the incidence vectors of the independent sets of a matroid M(P(g)). Another gives an easy description of the vertices of P(g). We will show how these ideas provide beautiful, but complicated, polytime algorithms for the possibly useful optimum branching system problem. |
| 关 键 词: | 算法; 多拟阵; 子模性 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2021-02-04：nkq |
| 最后编审: | 2021-02-04：nkq |
| 阅读次数: | 67 |