Скорее нужно найти некоторый алгоритм, который бы давал решение сильно лучше, чем получалось бы при случайном выборе набора индексов
Скажите, а не может ли оказаться, что хорошие результаты получаются именно при случайном выборе точки

для каждого момента времени?
Вот какие мысли у меня были.
Собственные значения

матрицы

, в силу её структуры, неотрицательны. Чтобы

была обратимой, среди

не должно быть и нулевого. Тогда все

.
Собственные значения

матрицы

равны

, и аналогично все

.
Мы хотим, чтобы след матрицы

был малым. Так как

, то должно быть малым максимальное из

. То есть должно быть большим минимальное из

.
Этого, однако, не будет, если столбцы матрицы

будут почти линейно зависимы, то есть если прибавлением к одному из столбцов

(с номером

) линейной комбинации остальных столбцов мы можем сделать все элементы

-го столбца очень малыми числами. Тогда у

одно из собственных значений

будет очень малым, что, как мы выяснили выше, плохо.
Теперь представим, что точек

очень-очень много и они примерно равномерно распределены по сфере (я буду считать, что она единичного радиуса). Попробуем несколько «детерминированных» стратегий выбора точки для каждого момента времени

. Можно, например, выбирать

, ближайшую к

. Но тогда числа, стоящие во втором столбце

, будут близки к

. Отняв от второго столбца четвёртый, получим во втором очень малые числа.
Можно, наоборот, подбирать

так, чтобы векторы

и

были почти ортогональны. Тоже ничего хорошего: во втором столбце сразу будут почти нули. И вообще, стремление к тому, чтобы скалярные произведения

и/или

были заданными константами для всех

, делает столбцы

почти линейно зависимыми.
Ну хорошо, а давайте для части

выбирать точку

, ближайшую к

, а для другой части — ближайшую к

. Результат тот же.
Тут я и подумал, что, возможно, случайный выбор точки

будет давать результат, близкий к оптимальному.