On the simplification of a placement problem

The authors consider the placement of heterogeneous modules to minimize the expected value of the distance required for an intermodule communication, where the expectation is taken with respect to a given matrix of intermodule communication probabilities. One way the placement problem could be simplified would be to select a `footprint´ with the property that all modules of the optimum placement occupy locations in the footprint, and there are no vacancies within the footprint region. If such footprints were known, they could be precomputed for each system size and the optimization problem would be reduced to a search of placements meeting the footprint constraint. However, it is shown that a footprint does not exist for the placement problem with the objective of minimizing the expected communication distance