关于图的导出森林独立系统

本文研究图的导出森林独立系统.在这个独立系统中,独立集是指导出子图不含圈的点子集.文中证明了图G的导出森林独立系统是拟阵当且仅当G是块森林.文中同时给出了在强弦图上求最大导出森林的多项式算法.     

Boolean sublattices connected with minimization problems on matroids

It is noted that the decomposition of a network presented by J.C. Picard and M. Queyranne through an algorithmic argument may be defined from a general lattice-theoretic result for more general problems for which the equalities of maximum-flow minimum-cut type hold.     

Maximizing non-monotone submodular set functions subject to different constraints: Combined algorithms

We study the problem of maximizing constrained non-monotone submodular functions and provide approximation algorithms that improve existing algorithms in terms of either the approximation factor or simplicity. Different constraints that we study are exact cardinality and multiple knapsack constraints for which we achieve (0.25−?)-factor algorithms.We also show, as our main contribution, how to use the continuous greedy process for non-monotone functions and, as a result, obtain a 0.13-factor approximation algorithm for maximization over any solvable down-monotone polytope.