2
$\begingroup$

Suppose we have a d-dimensional array A (d > 1) where each dimension has length n. The array is given in sparse notation as input, and the number of given non-zero elements is N. We want to find a contiguous range of indices for each dimension such that the sum of entries in the arising subarray "box" is maximized. For d=2 there is an O(N n log n) algorithm that is a modification of Kadane's O(n^3) original algorithm for a dense square array. However this sparse d=2 algorithm still requires a brute force search over ranges of rows, and straightforward extensions of the algorithm to higher dimensional arrays seem to be exponential complexity if the dimension d is not fixed.

So is it an NP-hard problem when d is not fixed? I'm particularly interested in the case where N = n, and each d-1 dimensional "flat" (fix one index in one dimension, and let all other indices vary between 1 and n) has exactly one non-zero element (a generalization of a product of a diagonal matrix and permutation matrix for the case d=2). Maybe this case is NP-hard? But the general case of a sparsely presented array is also of interest. Note this includes the case N=n^d, i.e. a dense array, but I'm wondering if the running time can be given in terms of N like the d=2 case, so that the running time can potentially be reduced when the array is sparse. Even if the problem is NP-hard for some N, I'd still be interested to find algorithms as efficient as possible, e.g. in terms of N. But the N=n case I described is the most important to me.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.