“结构化处理器网络UET任务不可逼近和多项式时间逼近算法”的勘误表

1.相关的工作

本勘误表致力于在[1]．

1．1.复杂的结果

表格1给出前面的复杂性结果。

1．2．近似的结果

如果网络是环形的，则有两个近似结果2]算法如下所示。(我)一般情况下，性能比的上限为，存在性能比等于的实例［3.]．(2)如果处理器数量为偶数，则上限可提高为，且存在一个实例，使性能比等于［4]．

本文的前两个推论必须用以下两个推论代替。

先前的复杂性导致了处理器网络模型。

推论1.1。决定一个实例是否；；，与有一个长度最多为3的时间表吗推进与．

证明。参见[3.]．

此外，还可以推导出非逼近结果。

推论1.2。不存在性能界限小于的多项式时间算法除非的问题；；和；；，与．

证明。参见[3.]．

本文的其余部分将结果推广到深度一的二部，并在以下定理和两个推论中给出了主要的复杂性结果。

定理1.3。决定一个实例是否，，有一个长度最多为3的时间表吗完成了。

推论1.4。决定一个实例是否；；，与有一个长度最多为3的时间表吗的推进。

推论1.5。不存在性能界限小于的多项式时间算法除非的问题；；和；；，与．

参考文献

1. M. Bouznif和R. Giroudeau，“基于结构化处理器网络的UET任务的不可逼近和多项式时间逼近算法”，运筹学研究进展， 2011年第4期，文章编号476939,20页，2011年。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
2. V. J. Rayward-Smith，“基于单元间处理器通信延迟的UET调度”，离散应用数学第18卷第2期1，页55 - 71,1987。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
3. c . Lahlou在处理过程中顺序:复杂和近似博士论文，巴黎第六大学，1998年。
4. 环网上单位处理和通信时间的调度:近似结果欧洲竞赛论文集，第539-542页，施普林格，1996。视图:谷歌学术搜索
5. C. Picouleau，“在任意网络上的UET-UCT时间表”，巴黎第六大学Blaise Pascal, LITP技术代表，1994。视图:谷歌学术搜索
6. R.吉鲁多(R. Giroudeau)， j.c. König和B.瓦莱里(B. Valery)，《日程安排》(Scheduling)$UET$星型网络的任务:复杂性和近似值，”4、。运筹学研究季刊，第9卷，第5期。1，页29-48,2011。视图:出版商的网站|谷歌学术搜索

版权

版权所有©2012 M. Bouznif和R. Giroudeau。这是一篇发布在知识共享署名许可协议，允许在任何媒介上不受限制地使用、传播和复制，但必须正确引用原作。