论文标题
图表上本地定义的独立系统
Locally Defined Independence Systems on Graphs
论文作者
论文摘要
图表上定义的独立系统的最大化是组合优化问题的概括，例如最大$ b $匹配，未加权的max-sat，matchoid和最大定时匹配问题。在本文中，我们考虑了本地甲骨文模型下的问题，以使用局部近似性来研究问题的全局近似性。我们首先分析了模型下最大化的两种简单算法固定排序和贪婪，这表明它们没有恒定的近似比。在这里，算法固定订单和贪婪分别以固定和贪婪的顶点订单应用局部甲壳。然后，我们提出了$ K $ - 定量图的两种近似算法，其近似值为$α+2k -2 $和$αk$，其中$α$是局部甲壳的近似值。第二个可以推广到HyperGraph设置。我们还提出了一种$（α+ k）$ - 二分图的近似算法，其中一个顶点中的本地独立系统是具有独立甲骨文的$ k $ - 系统。
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 $α+2k -2$ and $αk$, where $α$ is the approximation ratio of local oracles. The second one can be generalized to the hypergraph setting. We also propose an $(α+ k)$-approximation algorithm for bipartite graphs, in which the local independence systems in the one-side of vertices are $k$-systems with independence oracles.
