Approximating chromatic sum coloring of bipartite graphs in expected polynomial time

Известно что если $P \neq NP$ то задача аппроксимации суммарной раскраски двудольных графов не может быть осуществлена в полиномиальное время с точностью $1-\varepsilon$ для некоторой константы $\varepsilon$. Мы предлагаем для сколь угодно малого $\varepsilon>0$ приближенный алгоритм для данной проблемы который работает за полиномиальное в среднем время.