@InProceedings{Prusa-Werner-EMMCVPR2015, IS = { zkontrolovano 26 Jun 2015 }, UPDATE = { 2015-02-03 }, title = {How Hard Is the LP Relaxation of the Potts Min-Sum Labeling Problem?}, author = {Pr{\accent23 u}{\v s}a, Daniel and Werner, Tom{\' a}{\v s}}, affiliation = {13133-13133}, authorship = {50-50}, year = {2015}, day = {13-16}, month = {January}, venue = {Hong Kong, China}, isbn = {978-3-319-14611-9}, booktitle = {EMMCVPR 2015: Proceedings of the 10th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition}, volume = {8932}, series = {Lecture Notes in Computer Science}, editor = {Tai, Xue-Cheng and Bae, Egil and Chan, Tony F. and Lysaker, Marius}, doi = {10.1007/978-3-319-14612-6_5}, url = {http://dx.doi.org/10.1007/978-3-319-14612-6_5}, publisher = {Springer}, address = {Heidelberg, Germany}, keywords = {Markov random field, discrete energy minimization, valued constraint satisfaction, linear programming relaxation, uniform metric labeling problem, Potts model}, annote = {An important subclass of the min-sum labeling problem (also known as discrete energy minimization or valued constraint satisfaction) is the pairwise min-sum problem with arbitrary unary costs and attractive Potts pairwise costs (also known as the uniform metric labeling problem). In analogy with our recent result, we show that solving the LP relaxation of the Potts min-sum problem is not significantly easier than that of the general min-sum problem and thus, in turn, the general linear program. This suggests that trying to find an efficient algorithm to solve the LP relaxation of the Potts min-sum problem has a fundamental limitation. Our constructions apply also to integral solutions, yielding novel reductions of the (non-relaxed) general min-sum problem to the Potts min-sum problem.}, pages = {57-70}, book_pages = {506}, project = {GACR P202/12/2071, FP7-ICT-270138 DARWIN}, language = {English}, psurl = {PDF}, }