One possible project would flow out of the circular permutations discussed in
the following two papers:
Backtracking Algorithms
An Alternative Problem for Backtracking and Bounding
Since they depend on a backtracking algorithm, they can be the basis for an “embarrassing parallel” solution.
The generalized problem would have two components:
As you can see from the second paper, the smallest “MaxSum” does not increase smoothly with the size of the permutation vector.
One exploratory approach would be a backtracking version in which there is a trial value for MaxSum. When, however, the processing of a complete permutation discovers that it in fact has a smaller value, the global MaxSum is updated. This amounts to doing the backtracking without counting successful permutations but instead discovering the smallest possible value for “MaxSum”.
There is a construction which establishes that MaxSum can be 2N+1:
Build the vector from the extreme values, alternating, until you come to the
middle, as in “1 6 2 5 3 4”. Above n=4, the largest triple sum in this
configuration is 2N+1.
In the specimen shown, 6 + 2 + 5 = 13 = 2*6 + 1 — see
CircDuPlay.java.
The project will be done in MPI, using a self-scheduling approach for the worker processes. Each worker process will receive messages from the master process. The message type will determine whether the worker is determining the smallest MaxSum or is counting up permutations. The message accompanying this type will be a two-element integer array: vector size, and MaxSum (either the one to use or the initial trial one). In addition, there will be a message type for passing the initial vector to the worker. The assumption is that the worker processes will permute all but two cells. The message back from the worker to the master will give a single integer, either the smallest MaxSum encountered or the number of permutation encountered based on the MaxSum provided.