ON THE HARDNESS OF APPROXIMATING OPTIMUM SCHEDULE PROBLEMS IN STORE-AND-FORWARD NETWORKS

Scheduling a set of messages in a store and forward network means assi gning to them network resources in order to deliver each message to it s respective destination, The goal of typical scheduling problems is t o devise strategies of assignments that minimize the delivery time of all messages or, alternatively, their total end-to-end delay, Both pro blems have been proven to be network performance (NP)-hard even under very restrictive hypothesis [3], [6]. In this paper, we study the comp utational complexity of approximating the minimum end-to-end delay, Un fortunately, it turns out that finding an approximated solution with a pproximation ratio smaller than k(1/10) is as difficult as finding the optimal solution (where k is the number of messages in the network), More precisely, approximating the optimum delay is NP-hard even when a nonconstant approximation ratio is allowed, This result holds also in the case of layered networks, We then prove that if we consider a par ticular class of local schedules (i.e., distributed strategies that ca n only use information about limited regions of the network) then the approximation error cannot be bounded by any sublinear function in k, Such results also provide a lower bound on the approximation of the mi nimum delivery time problem, Thus, if the attention is restricted to p olynomial-time algorithms, the only possibility is designing heuristic s that behave well on average, As a first step to this aim, we evaluat e the expected approximation error of some simple heuristics using sev eral experimental tests.