图 书 馆
含噪声部分信息的相关聚类Correlation Clustering with Noisy Partial Information |
|
| 课程网址: | https://videolectures.net/videos/colt2015_vijayaraghavan_partial_... |
| 主讲教师: | Aravindan Vijayaraghavan |
| 开课单位: | 信息不详。欢迎您在右侧留言补充。 |
| 开课时间: | 2015-08-20 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | In this paper, we propose and study a semi-random model for the Correlation Clustering problem on arbitrary graphs G. We give two approximation algorithms for Correlation Clustering instances from this model. The first algorithm finds a solution of value $(1+ \delta)optcost + O_{\delta}(n\log^3 n)$ with high probability, where \optcost is the value of the optimal solution (for every $\delta > 0$). The second algorithm finds the ground truth clustering with an arbitrarily small classification error $\eta$ (under some additional assumptions on the instance). |
| 关 键 词: | 聚类问题; 高概率：真理聚类 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2025-04-07：zsp |
| 最后编审: | 2025-04-07：zsp |
| 阅读次数: | 7 |