求解上模函数的近似算法

梁国宏 刘光荣 宋修朝 冯军庆

[摘要]根据上模函数的定义,给出了在某个有限集合上的近似模函数的定义及其性质,主要研究了求解上模函数的近似算法及模函数的算法。

[关键词]组合优化问题 上模函数 近似模函数算法

设V是一个非空有限集合,如果

则称f∶2琕是上模函数。类似地,上式(1)中取“≤”时称f为下模函数;取上式(1)中“=”时称f为模函数。

定义1:已知上模函数f∶2琕→R,如果模函数h璶∶2琕→R满足:

h璶(A)≤g(A),歇罺,则称函数h璶是函数g的近似模函数.特别地,如果函数h璶是函数g的近似模函数,且h璶(A璶)≤g(A璶),歇璶罺,则称函数h璶是函数g的在A璶上的完全近似模函数。

性质1:假设g∶2琕→R是一个上模函数,π是V的任一排列.设W={π(1),π(2),…,π(i)}有W﹟V|=V

定义函数h∶V→R:

显然有有下列性质:

算法1:给定上模函数g与f,求f-g的近似最小值。

步骤如下:

1 给定集V的任意排列π0,n=0,min=∞;

2 h璶=(g,π﹏-1)的模近似, ,π﹏+1,表示A璶开始的任意排列,n=n+1;

3 如果val

性质2:上述所提到的每个h是g的展开基拟阵的一个顶点,且这个顶点可以合适的置换中得到。此外,如果c是R﹟V|中的一个向量,那么上面的贪婪算法求解以下的优化问题:

算法2:给定上模函数g和π排列,求上模函数g的模近似函数h.

步骤如下:

1

2

3 如果n≤|V|,则转2;否则,停止计算。

算法1给出了求一个给定的上模函数g与f的f-g的近似最小值的有效算法;算法2给出了求上模函数g的模近似函数 的算法。

参考文献:

[1]M.Narasimhan and J.Bilmes."PAC learning bounded treewidth graphical models".Proceed-ings of the 20th conference on Uncertainty in Artificial Intelligece,2004.

[2]M,Grotschel,L.Lovasz and Schrijver."The ellipsoid method and its consequences in combinatorial optimization".In Combinatorica, v.1,Pages 169-197,1981.

[3]Mukund Narasimhan and Jeff Bilmes,"A submodular-supermodular Procedure with applications to discriminative structure learning".in Combinatorial structures and their applications,1970.