How Hard Is the LP Relaxation of the Potts Min-Sum Labeling Problem?

1. Boros, E., Hammer, P.L.: Pseudo-Boolean optimization. Discrete Applied Mathematics 123(1-3), 155–225 (2002)

   Article  MATH  MathSciNet  Google Scholar 

2. Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Analysis and Machine Intelligence 23(11), 1222–1239 (2001)

   Article  Google Scholar 

3. Chekuri, C., Khanna, S., Naor, J., Zosin, L.: A linear programming formulation and approximation algorithms for the metric labeling problem. SIAM Journal on Discrete Mathematics 18(3), 608–625 (2005)

   Article  MATH  MathSciNet  Google Scholar 

4. Chuzhoy, J., Naor, J.: The hardness of metric labeling. SIAM J. Computation 36(5), 1376–1386 (2007)

   Article  MATH  MathSciNet  Google Scholar 

5. Kappes, J.H., Andres, B., Hamprecht, F.A., Schnörr, C., Nowozin, S., Batra, D., Kim, S., Kausler, B.X., Lellmann, J., Komodakis, N., Rother, C.: A comparative study of modern inference techniques for discrete energy minimization problem. In: Conf. on Computer Vision and Pattern Recognition (2013)

   Google Scholar 

6. Kleinberg, J., Tardos, E.: Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields. J. ACM 49(5), 616–639 (2002)

   Article  MathSciNet  Google Scholar 

7. Koster, A., van Hoesel, S.P.M., Kolen, A.W.J.: The partial constraint satisfaction problem: Facets and lifting theorems. Operations Research Letters 23(3-5), 89–97 (1998)

   Article  MATH  MathSciNet  Google Scholar 

8. Kovtun, I.: Partial optimal labelling search for a NP-hard subclass of (max,+) problems. In: Conf. German Assoc. for Pattern Recognition, pp. 402–409 (2003)

   Google Scholar 

9. Osokin, A., Vetrov, D., Kolmogorov, V.: Submodular decomposition framework for inference in associative Markov networks with global constraints. In: IEEE Conf. on Computer Vision and Pattern Recognition, pp. 1889–1896 (2011)

   Google Scholar 

10. Průša, D., Werner, T.: Universality of the local marginal polytope. In: Conf. on Computer Vision and Pattern Recognition, pp. 1738–1743. IEEE Computer Society (2013)

    Google Scholar 

11. Rother, C., Kolmogorov, V., Lempitsky, V.S., Szummer, M.: Optimizing binary MRFs via extended roof duality. In: Conf. on Computer Vision and Pattern Recognition (2007)

    Google Scholar 

12. Schlesinger, D., Flach, B.: Transforming an arbitrary MinSum problem into a binary one. Tech. Rep. TUD-FI06-01, Dresden University of Technology, Germany (April 2006)

    Google Scholar 

13. Shlezinger, M.I.: Syntactic analysis of two-dimensional visual signals in noisy conditions. Cybernetics and Systems Analysis 12(4), 612–628 (1976)

    Google Scholar 

14. Swoboda, P., Savchynskyy, B., Kappes, J.H., Schnörr, C.: Partial optimality via iterative pruning for the Potts model. In: Conf. on Scale Space and Variational Methods in Computer Vision (2013)

    Google Scholar 

15. Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., Tappen, M., Rother, C.: A comparative study of energy minimization methods for Markov random fields with smoothness-based priors. IEEE Trans. on Pattern Analysis and Machine Intelligence 30(6), 1068–1080 (2008)

    Article  Google Scholar 

16. Živný, S.: The Complexity of Valued Constraint Satisfaction Problems. Cognitive Technologies. Springer (2012)

    Google Scholar 

17. Wainwright, M.J., Jordan, M.I.: Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning 1(1-2), 1–305 (2008)

    MATH  Google Scholar 

18. Werner, T.: A linear programming approach to max-sum problem: A review. IEEE Trans. Pattern Analysis and Machine Intelligence 29(7), 1165–1179 (2007)

    Article  Google Scholar 

Download references