An illustrative pair of unary cost functions combines into a weighted objective on three possible values. The extended problem allows a family of such costs while requiring the assignment to satisfy a fixed constraint language. Research source
About this paper
Extends minimum cost homomorphisms to a broader optimization framework with conservative constraint languages.
A family of cost functions unifies minimum cost homomorphisms and maximum solution problems. Under restrictions on the cost functions, the paper proves a complexity dichotomy, including one for the conservative maximum solution problem.
Citation
BibTeX
@inproceedings{takhanov2010extensionsminimumcosthomomorphism,
title = {Extensions of the minimum cost homomorphism problem},
author = {Takhanov, Rustem},
year = {2010},
booktitle = {COCOON 2010},
eprint = {1210.2260},
archivePrefix = {arXiv},
url = {https://arxiv.org/pdf/1210.2260}
}