The maximization for the independence systems defined on graphs is a generalization of combinatorial optimization problems such as the maximum $b$-matching, the unweighted MAX-SAT, the matchoid, and the maximum timed matching problems. In this paper, we consider the problem under the local oracle model to investigate the global approximability of the problem by using the local approximability. We first analyze two simple algorithms FixedOrder and Greedy for the maximization under the model, which shows that they have no constant approximation ratio. Here algorithms FixedOrder and Greedy apply local oracles with fixed and greedy orders of vertices, respectively. We then propose two approximation algorithms for the $k$-degenerate graphs, whose approximation ratios are $\alpha +2k -2$ and $\alpha k$, where $\alpha$ is the approximation ratio of local oracles. The second one can be generalized to the hypergraph setting. We also propose an $(\alpha + k)$-approximation algorithm for bipartite graphs, in which the local independence systems in the one-side of vertices are $k$-systems with independence oracles.
翻译:图形上定义的独立系统最大化是组合优化问题的一般化, 如最大值对齐、 未加权的 MAX- SAT、 配对类和最大时间匹配问题。 在本文中, 我们考虑本地孔雀模型下的问题, 通过使用本地接近度来调查问题的全球近似性。 我们首先分析两种简单的算法: 固定值和贪婪, 以便在模型下最大化, 这表明它们没有恒定的近似率 。 这里的固定值和贪婪算法分别应用固定和贪婪的脊椎定序的本地孔雀。 我们然后为美元- 脱基因图案提出两种近似算法, 其近似率为 $+2k-2 和 $ alpha k 。 $\ alpha 是本地孔雀斑的近似率率。 第二种算法可以普遍化为高度设置 。 我们还提议用 $ (alpha+ k) 美元- appregrocifical 算s 系统, 其独立度为双部的当地标准。