Search

Through recent technical advances, multiple resources can be connected to provide a computing grid for processing computationally intensive applications. We build on an approach, termed sequential grid computing, that takes [...]

Exact algorithms that use two types of pruning schemes employed in labeling procedures are developed to solve even large size problems rapidly. One type of pruning adopts the concept of local preference relations while the other applies relaxations. Two algorithms are developed which both contain equal preference relation but two varied relaxations. Both algorithms solve even large problems by citing a very small percentage of all paths.

We present a technique to construct efficient belief network structures for application areas where large amounts of data are available and information on the ordering of the variables can be obtained from domain experts. We identify classes of networks that are efficient for propagating beliefs. We formulate the problem as one of determining the belief network representation from a given class that best represents the data. We use the I-Divergence measure which is known to have certain desirable properties for evaluating different approximations. We present some theoretical findings that characterize the nature of solutions that are obtained. These theoretical results lead to an efficient solution procedure for finding the best network representation. We also discuss other information that may be reasonably obtained from experts, and show how such information leads to improving the efficiency of the technique to find the best network structure. Index Terms - Belief networks, expert systems, information theory, knowledge acquisition, probabilistic reasoning, scoring rules.

An interactive approach for solving the bicriterion shortest path problem is presented. The approach makes use of domination cones to evaluate a large number of Pareto-optimal solutions, thereby, enabling the user to analyze a small fraction of all Pareto-optimal paths and at the same time reducing the computational effort required to identify the solutions to be evaluated. Results obtained from the application of the proposed interactive procedure to large grid networks with varying topographical characteristics show that the method is capable of arriving at the optimal solution for the bicriterion shortest path problem.

A file allocation problem model that minimizes cost file allocation is presented. Moreover, this model assures that in the worst case, response time for each query is feasible, and this results in a 0/1 integer programming problem. Then, a Lagrangian relaxation-based algorithm is developed and tested on several classes of problems. Results show that the model, in conjunction with the solution procedure, is accurate and efficient.