以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 算法理论与分析 』  (http://bbs.xml.org.cn/list.asp?boardid=60)
----  簡單証 NP-complete問題  (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=88076)

--  作者：tonald
--  发布时间：11/30/2010 10:51:00 PM

--  簡單証 NP-complete問題
怎樣 使用 subset sum problem 證 multi-process scheduling problem 是NPC?
用partition 我懂，這個我不懂…

附上multi-process scheduling problem的定義
A multiset A of tasks, a measurement of the time required
for each task l: A-->N, a deadline (real number) D;
Is there a partition of A into m disjoint sets such that the
total time (sum of l(a)) for every element in a partition is always at
most D?

W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 1,796.875ms