Approximating chromatic sum coloring of bipartite graphs in expected polynomial time

Abstract

It is known that if P≠NP the sum coloring problem cannot be approximated within for some constant . We propose for arbitrary small an approximation scheme for this problem that works in expected polynomial time.

Keywords

• проблема хроматической раскраски
• двудольные графы
• полиномиальное в среднем время