TRANSFORMING AN ARBITRARY MINSUM PROBLEM INTO A BINARY ONE
Dmitrij Schlesinger, Boris Flach · 2006
ABSTRACT. In this report we show, that an arbitrary MinSum problem (i.e. a MinSum problem with an arbitrary finite set of states) can be adequately transformed into a binary one (i.e. into a MinSum problem with only two states). Consequently all known results for binary MinSum problems can be easily extended to the general case. For instance it gives the possibility to solve exactly submodular MinSum problems with more than two states by using MinCut-MaxFlow based technics. CONTENTS