Akbar Rafiey

Given two (di)graphs $G$, $H$ and a cost function $c:V(G)\times V(H) \to \mathbb{Q}_{\geq 0}\cup\{+\infty\}$, in the minimum cost homomorphism problem, MinHOM($H$), we are interested in finding a homomorphism $f:V(G)\to V(H)$ (a.k.a $H$-coloring)...

Abstract: The problem of maximizing nonnegative monotone submodular functions under a certain constraint has been intensively studied in the last decade, and a wide range of efficient approximation algorithms have been developed for this problem...