V🇺
Алексей
(E,Z) не матройд. Он вроде удовлетворяет 3-м аксиомам
третья аксиома не выполняется - если взять A={e, f} и B={g}, то не найдется x из A/B чтобы B+{x} было в Z
Size: a a a
2020 April 18
А
третья аксиома не выполняется - если взять A={e, f} и B={g}, то не найдется x из A/B чтобы B+{x} было в Z
Да! Окончательно понял теперь
А
If x and y are two independent sets, and x has more elements than y,
then there exists an element in x which is not in y that when added
to y still gives an independent set. This is called the independent set
exchange property.
then there exists an element in x which is not in y that when added
to y still gives an independent set. This is called the independent set
exchange property.
А
Спасибо за подсказку
А
@isenbaev копаясь в матройдах в одной книжке наткнулся на фразу: While matroids serve as a good abstract model for greedy algorithms,
a general model for dynamic programming is being currently developed.
a general model for dynamic programming is being currently developed.
V🇺
Алексей
@isenbaev копаясь в матройдах в одной книжке наткнулся на фразу: While matroids serve as a good abstract model for greedy algorithms,
a general model for dynamic programming is being currently developed.
a general model for dynamic programming is being currently developed.
уже страшно
А
уже страшно
И мне очень страшно стало - когда я увидел ту математику, которая идет в работах по моделям для ДП)
f
Дан граф с n (100000) вершинами, m(300000) ребрами. Из каждой вершины выходит не более D(12) ребер. Какая будет асимптотика, и как ее доказать, если перебрать для каждой вершины графа маску ее соседей? (2^12 * 12, если соседей 12.)
S
У кого-нибудь есть опыт с Ceres на несколько миллионов термов? Хочу понять, как его сконфигурить, чтобы адекватно быстро работал.
Каждый терм задаю отдельно. Зависит примерно от 10 переменных. Но они у всех термов запутаны. Якобианы считаю сам.
Каждый терм задаю отдельно. Зависит примерно от 10 переменных. Но они у всех термов запутаны. Якобианы считаю сам.
S
Только создание задачи на 7 лямов занимает 2 минуты, что как-то стремно.
S
Вывод на CGNR занимает минут 7, спарс-холески уходит в аут минимум минут на 30.
V🇺
У кого-нибудь есть опыт с Ceres на несколько миллионов термов? Хочу понять, как его сконфигурить, чтобы адекватно быстро работал.
Каждый терм задаю отдельно. Зависит примерно от 10 переменных. Но они у всех термов запутаны. Якобианы считаю сам.
Каждый терм задаю отдельно. Зависит примерно от 10 переменных. Но они у всех термов запутаны. Якобианы считаю сам.
а задача какая?
S
min norm1 * \sum_i (\log y_i - \sum_{j in S_i} \log x_j)^2 + norm2 * lambda * Reg(x)
S
|S_i| <= 10
S
x_j \in [0, 1], y_i \in [0, 1]
S
Есть такая же, но на произведении без логарифмов
S
Немного о природе S_i -- это ребра путей в графе малого диаметра
S
Таких путей в графе много, и они, ясно, друг с другом активно пересекаются
V🇺
а какого порядка размерности x и y?
V🇺
если есть возможность использовать GPU (что на таком масштабе возможно осмысленно), можно посмотреть на optlang.org