Поиск подматрицы с максимальной суммой (актуальная верхняя оценка)

У меня незначительные замечания:
1) Есть чуть более простая жадность для одномерного случая (у меня она работает чуть быстрее):

int sum = 0, ans = a[0];
for (int i = 0; i < n; ++i)
{
  sum += a[i];
  ans = max(ans, sum);
  if (sum < 0)
    sum = 0;
}

Кстати это называется алгоритм Kadane, а n^2*m алгоритмом Bentley
(есть ссылка в Takaoka 2002)

Интересно, что gcc строку ans = max(ans, sum); оптимизирует на ура (т.е. вручную улучшить не удалось),
и самое долгое место это if (sum < 0) (проверка бита знака числа).

2) В той же статье Takaoka двумерная задача сводится к задаче APSP (всех пар кратчайших путей во взвешенном графе). Т.е. они асимптотически эквивалентны.
Но с 2002 года только сам Takaoka улучшил оценку 2 раза, а всего она менялась не менее 7 раз и лучшая из того, что я знаю:
T. Chan 2007: n^3 * log^3 log n / log^2 n.

3) Когда мне пришлось реализовывать этот алгоритм (строго говоря предыдущий 2006-ого года), я попытался сравнить его константу с Флойдом. Что-то у меня получалось, даже при самых грубых оценках, что он начнет обгонять Флойда при n >= 2^50.
Сложно себе представить запуск Флойда при таких ограничениях, даже при самых оптимистичных прогнозах на развитие процессоров ((

4) Важным же замечанием является то, что открытым и наиболее интересным является вопрос о решении APSP за время n^(3 - eps). Для любого малой константы eps.

5) Ахо и Ульман показали, что вычисление APSP эквивалентно одному умножению матриц в тропической полугруппе
(вместо сложения - min, вместо умножения - арифметическое сложение). Когда хотят улучшить оценку, эту задачу все и решают, а не все выше означенные.

Ссылка на статью: http://www.cs.uwaterloo.ca/~tmchan/moreapsp.pdf