# Erratum to “Inapproximability and Polynomial-Time Approximation Algorithm for UET Tasks on Structured Processor Networks”

Authors: M. Bouznif; R. Giroudeau
Journal: Advances in Operations Research
 (2012)

---

## Body

## 1. Related Works

This erratum is devoted to give some precisions on the related works in stand of view complexity and approximation given in [1].


### 1.1. Complexity Results

Table1 gives the previous complexity results.Table 1
TopologyPrecedence graphComplexityReferenceUnbounded chaintree𝒩𝒫-complete[5]anti-tree𝒩𝒫-completeStartree𝒩𝒫-complete[5]Cycle/chainprec/bipartiteofdepthtwoρ≥4/3[3]Starprecρ≥6/5[6]


### 1.2. Approximation Results

If the network is a ring, there are two approximation results for Rayward-Smith’s [2] algorithm as follows.(i)
In the general case, the performance ratio is upper bounded bym/2+3/2-1/m, and there exists an instance for which the performance ratio is equal to m/8+1/2 [3].(ii)
If the number of processors is even, the upper-bound can be improved to1+(3/8)m-1/2m, and there exists an instance such that the performance ratio is equal to ⌈m⌉ [4].The first two corollaries of the paper must be replaced by the two following corollaries.Previous complexity results on the processors network model.Corollary 1.1.
The problem of deciding whether an instance of(P,G*)∣β; cij=d(πℓ,πk); pi=1, dup∣Cmax with G*∈𝒢 has a schedule of length at most three is 𝒩𝒫-complete with β∈{prec,bipartiteofdepthtwo}.Proof.
See [3].Moreover, nonapproximability results can be deduced.Corollary 1.2.
No polynomial-time algorithm exists with a performance bound less than4/3 unless 𝒫=𝒩𝒫 for the problems (P,G*)∣β; cij=d(πl,πk); pi=1∣Cmax and (P,G*)∣β; cij=d(πℓ,πk); pi=1, dup∣Cmaxβ∈{prec,bipartiteofdepthtwo} with G*∈𝒢.Proof.
See [3].The rest of the paper is devoted to extend the result to the bipartite of depth one and the main complexity result is given in the following theorem and two corollaries.Theorem 1.3.
The problem of deciding whether an instance of(P,G*)∣bipartiteofdepthone, cij=d(πℓ,πk)=1, pi=1∣Cmax has a schedule of length at most three is 𝒩𝒫-complete.Corollary 1.4.
The problem of deciding whether an instance of(P,G*)∣bipartiteofdepthone; cij=d(πℓ,πk); pi=1, dup∣Cmax with G*∈𝒢 has a schedule of length at most three is 𝒩𝒫-complete.Corollary 1.5.
No polynomial-time algorithm exists with a performance bound less than4/3 unless 𝒫=𝒩𝒫 for the problems (P,G*)∣bipartiteofdepthone; cij=d(πℓ,πk); pi=1∣Cmax and (P,G*)∣bipartiteofdepthone; cij=d(πℓ,πk); pi=1, dup∣Cmax with G*∈𝒢.


## 1.1. Complexity Results

Table1 gives the previous complexity results.Table 1
TopologyPrecedence graphComplexityReferenceUnbounded chaintree𝒩𝒫-complete[5]anti-tree𝒩𝒫-completeStartree𝒩𝒫-complete[5]Cycle/chainprec/bipartiteofdepthtwoρ≥4/3[3]Starprecρ≥6/5[6]


## 1.2. Approximation Results

If the network is a ring, there are two approximation results for Rayward-Smith’s [2] algorithm as follows.(i)
In the general case, the performance ratio is upper bounded bym/2+3/2-1/m, and there exists an instance for which the performance ratio is equal to m/8+1/2 [3].(ii)
If the number of processors is even, the upper-bound can be improved to1+(3/8)m-1/2m, and there exists an instance such that the performance ratio is equal to ⌈m⌉ [4].The first two corollaries of the paper must be replaced by the two following corollaries.Previous complexity results on the processors network model.Corollary 1.1.
The problem of deciding whether an instance of(P,G*)∣β; cij=d(πℓ,πk); pi=1, dup∣Cmax with G*∈𝒢 has a schedule of length at most three is 𝒩𝒫-complete with β∈{prec,bipartiteofdepthtwo}.Proof.
See [3].Moreover, nonapproximability results can be deduced.Corollary 1.2.
No polynomial-time algorithm exists with a performance bound less than4/3 unless 𝒫=𝒩𝒫 for the problems (P,G*)∣β; cij=d(πl,πk); pi=1∣Cmax and (P,G*)∣β; cij=d(πℓ,πk); pi=1, dup∣Cmaxβ∈{prec,bipartiteofdepthtwo} with G*∈𝒢.Proof.
See [3].The rest of the paper is devoted to extend the result to the bipartite of depth one and the main complexity result is given in the following theorem and two corollaries.Theorem 1.3.
The problem of deciding whether an instance of(P,G*)∣bipartiteofdepthone, cij=d(πℓ,πk)=1, pi=1∣Cmax has a schedule of length at most three is 𝒩𝒫-complete.Corollary 1.4.
The problem of deciding whether an instance of(P,G*)∣bipartiteofdepthone; cij=d(πℓ,πk); pi=1, dup∣Cmax with G*∈𝒢 has a schedule of length at most three is 𝒩𝒫-complete.Corollary 1.5.
No polynomial-time algorithm exists with a performance bound less than4/3 unless 𝒫=𝒩𝒫 for the problems (P,G*)∣bipartiteofdepthone; cij=d(πℓ,πk); pi=1∣Cmax and (P,G*)∣bipartiteofdepthone; cij=d(πℓ,πk); pi=1, dup∣Cmax with G*∈𝒢.



---

*Source: 543215-2012-05-28.xml*