| 摘要: |
| 本文提出了无向图(k,m)最优划分的一个近似算法,证明了这是一个产生近似最优解的多项式时间算法。在最坏情况下,该算法的性能保证为一个参数k所界定,这里k是与问题输入尺寸无关的。 |
| 关键词: |
| DOI： |
| 分类号: |
| 基金项目: |
|
| AN APPROXIMATION ALGORITHM ON GRAPH (K,M) OPTIMAL PARTITION PROBLEM |
|
Lu Qicheng
|
| Abstract: |
| In this paper we present an approximation algorithm for (k,m) optimal partition problem on an undirected graph. We show that this approximation algorithm which produces a near optimal solution runs in polynomial time. The performance ratio in the worst case is bounded by a parameter k, which is independent of input size of the problem. |
| Key words: |
