Efficient web searching using temporal factors

We study the issues involved in the design of algorithms for performing inf ormation gathering more efficiently, by taking advantage of anticipated var iations in access times in different regions at different times of the day or week. We look at the problem theoretically, as a generalisation of singl e processor sequencing with release times and deadlines, in which performan ce times (lengths) of the tasks can change in time. The new problem is call ed Variable Length Sequencing Problem (VLSP). We show that although the dec ision version of VLSP seems to be intractable in the general case, it can b e solved optimally for lengths 1 and 2. This result opens the possibility o f practicable algorithms to schedule searches efficiently when expected acc ess times can be categorised as either slow or fast. Some algorithms for mo re general cases are examined and complexity results derived. (C) 2001 Else vier Science B.V. All rights reserved.