---
_id: '14448'
abstract:
- lang: eng
  text: We consider the problem of solving LP relaxations of MAP-MRF inference problems,
    and in particular the method proposed recently in [16], [35]. As a key computational
    subroutine, it uses a variant of the Frank-Wolfe (FW) method to minimize a smooth
    convex function over a combinatorial polytope. We propose an efficient implementation
    of this subroutine based on in-face Frank-Wolfe directions, introduced in [4]
    in a different context. More generally, we define an abstract data structure for
    a combinatorial subproblem that enables in-face FW directions, and describe its
    specialization for tree-structured MAP-MRF inference subproblems. Experimental
    results indicate that the resulting method is the current state-of-art LP solver
    for some classes of problems. Our code is available at pub.ist.ac.at/~vnk/papers/IN-FACE-FW.html.
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
citation:
  ama: 'Kolmogorov V. Solving relaxations of MAP-MRF problems: Combinatorial in-face
    Frank-Wolfe directions. In: <i>Proceedings of the IEEE Computer Society Conference
    on Computer Vision and Pattern Recognition</i>. Vol 2023. IEEE; 2023:11980-11989.
    doi:<a href="https://doi.org/10.1109/CVPR52729.2023.01153">10.1109/CVPR52729.2023.01153</a>'
  apa: 'Kolmogorov, V. (2023). Solving relaxations of MAP-MRF problems: Combinatorial
    in-face Frank-Wolfe directions. In <i>Proceedings of the IEEE Computer Society
    Conference on Computer Vision and Pattern Recognition</i> (Vol. 2023, pp. 11980–11989).
    Vancouver, Canada: IEEE. <a href="https://doi.org/10.1109/CVPR52729.2023.01153">https://doi.org/10.1109/CVPR52729.2023.01153</a>'
  chicago: 'Kolmogorov, Vladimir. “Solving Relaxations of MAP-MRF Problems: Combinatorial
    in-Face Frank-Wolfe Directions.” In <i>Proceedings of the IEEE Computer Society
    Conference on Computer Vision and Pattern Recognition</i>, 2023:11980–89. IEEE,
    2023. <a href="https://doi.org/10.1109/CVPR52729.2023.01153">https://doi.org/10.1109/CVPR52729.2023.01153</a>.'
  ieee: 'V. Kolmogorov, “Solving relaxations of MAP-MRF problems: Combinatorial in-face
    Frank-Wolfe directions,” in <i>Proceedings of the IEEE Computer Society Conference
    on Computer Vision and Pattern Recognition</i>, Vancouver, Canada, 2023, vol.
    2023, pp. 11980–11989.'
  ista: 'Kolmogorov V. 2023. Solving relaxations of MAP-MRF problems: Combinatorial
    in-face Frank-Wolfe directions. Proceedings of the IEEE Computer Society Conference
    on Computer Vision and Pattern Recognition. CVPR: Conference on Computer Vision
    and Pattern Recognition vol. 2023, 11980–11989.'
  mla: 'Kolmogorov, Vladimir. “Solving Relaxations of MAP-MRF Problems: Combinatorial
    in-Face Frank-Wolfe Directions.” <i>Proceedings of the IEEE Computer Society Conference
    on Computer Vision and Pattern Recognition</i>, vol. 2023, IEEE, 2023, pp. 11980–89,
    doi:<a href="https://doi.org/10.1109/CVPR52729.2023.01153">10.1109/CVPR52729.2023.01153</a>.'
  short: V. Kolmogorov, in:, Proceedings of the IEEE Computer Society Conference on
    Computer Vision and Pattern Recognition, IEEE, 2023, pp. 11980–11989.
conference:
  end_date: 2023-06-24
  location: Vancouver, Canada
  name: 'CVPR: Conference on Computer Vision and Pattern Recognition'
  start_date: 2023-06-17
date_created: 2023-10-22T22:01:16Z
date_published: 2023-08-22T00:00:00Z
date_updated: 2023-10-31T12:01:24Z
day: '22'
department:
- _id: VlKo
doi: 10.1109/CVPR52729.2023.01153
external_id:
  arxiv:
  - '2010.09567'
intvolume: '      2023'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: ' https://doi.org/10.48550/arXiv.2010.09567'
month: '08'
oa: 1
oa_version: Preprint
page: 11980-11989
publication: Proceedings of the IEEE Computer Society Conference on Computer Vision
  and Pattern Recognition
publication_identifier:
  isbn:
  - '9798350301298'
  issn:
  - 1063-6919
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe
  directions'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2023
year: '2023'
...