Multispace search for minimizing the maximum nodal degree
Bin Du, Jun Gu, Wang Wei, Danny H. K. Tsang · 2002
Hajek and Sasaki (1988) showed that, for continuous traffic and packet radio network, the selection of paths that minimize the maximum nodal degree generates schedules of minimum-length. This result suggests that minimization of the maximum nodal degree provides good (although not necessarily optimal) performance in slotted networks with fixed-length packets. We give a multispace search algorithm that interplays structural operations in conjunction with a local search algorithm for the minimization of the maximum nodal degree. Structural operations disturb the environment of forming local minima, which makes multispace search a very natural approach to the problem. Experimental results indicate that this method has improved local search in terms of the solution quality and its sensitivity to the initial random assignment.