@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},
}