npc问题与近似算法内容摘要：
iijjMTt m a x iiTTApproximation Algorithm 近似算法 1 每次任意选择一个未安排的工作，将它安排在当前负载最小的机器上 •这是一个 2倍近似算法 Approximation Algorithm 证明： 1. 2. 假设 Mi 是负载最大的机器，工作 j是机器 i最后一个工作，我们有： 1 amp。 amp。 m a xjj jjO P T t O P T tm12*i j kkijT t t O P TmS o luti o n T O P T t O P T Approximation Algorithm 近似算法 2 每次选择一个未安排的工作中用时最多的，将它安排在当前负载最小的机器上 •这是一个 Approximation Algorithm 例 2： KCenter Problem 问题描述： 1. 给定一张图 G(V,E)满足 G 是 metric 2. 要求选择 k个点作为图的中心 3. 目标：最小化 m a x ( , )( : ( , ) m i n ( , ) )vVuCradi us di st v Cps di st v C di st v uApproximation Algorithm 近似算法 1 •每次假设图的 radius（至多 |E|个），然后执行以下算法 : 1. S=V C=empty 2. While S!=empty choose an arbitary v in S CC+v 3. if |C|=k succeed else increase radius。阅读剩余 0%
本站所有文章资讯、展示的图片素材等内容均为注册用户上传(部分报媒/平媒内容转载自网络合作媒体)，仅供学习参考。
用户通过本站上传、发布的任何内容的知识产权归属用户或原始著作权人所有。如有侵犯您的版权，请联系我们反馈本站将在三个工作日内改正。