---
_id: '916'
abstract:
- lang: eng
  text: We study the quadratic assignment problem, in computer vision also known as
    graph matching. Two leading solvers for this problem optimize the Lagrange decomposition
    duals with sub-gradient and dual ascent (also known as message passing) updates.
    We explore this direction further and propose several additional Lagrangean relaxations
    of the graph matching problem along with corresponding algorithms, which are all
    based on a common dual ascent framework. Our extensive empirical evaluation gives
    several theoretical insights and suggests a new state-of-the-art anytime solver
    for the considered problem. Our improvement over state-of-the-art is particularly
    visible on a new dataset with large-scale sparse problem instances containing
    more than 500 graph nodes each.
article_processing_charge: No
author:
- first_name: Paul
  full_name: Swoboda, Paul
  id: 446560C6-F248-11E8-B48F-1D18A9856A87
  last_name: Swoboda
- first_name: Carsten
  full_name: Rother, Carsten
  last_name: Rother
- first_name: Carsten
  full_name: Abu Alhaija, Carsten
  last_name: Abu Alhaija
- first_name: Dagmar
  full_name: Kainmueller, Dagmar
  last_name: Kainmueller
- first_name: Bogdan
  full_name: Savchynskyy, Bogdan
  last_name: Savchynskyy
citation:
  ama: 'Swoboda P, Rother C, Abu Alhaija C, Kainmueller D, Savchynskyy B. A study
    of lagrangean decompositions and dual ascent solvers for graph matching. In: Vol
    2017. IEEE; 2017:7062-7071. doi:<a href="https://doi.org/10.1109/CVPR.2017.747">10.1109/CVPR.2017.747</a>'
  apa: 'Swoboda, P., Rother, C., Abu Alhaija, C., Kainmueller, D., &#38; Savchynskyy,
    B. (2017). A study of lagrangean decompositions and dual ascent solvers for graph
    matching (Vol. 2017, pp. 7062–7071). Presented at the CVPR: Computer Vision and
    Pattern Recognition, Honolulu, HA, United States: IEEE. <a href="https://doi.org/10.1109/CVPR.2017.747">https://doi.org/10.1109/CVPR.2017.747</a>'
  chicago: Swoboda, Paul, Carsten Rother, Carsten Abu Alhaija, Dagmar Kainmueller,
    and Bogdan Savchynskyy. “A Study of Lagrangean Decompositions and Dual Ascent
    Solvers for Graph Matching,” 2017:7062–71. IEEE, 2017. <a href="https://doi.org/10.1109/CVPR.2017.747">https://doi.org/10.1109/CVPR.2017.747</a>.
  ieee: 'P. Swoboda, C. Rother, C. Abu Alhaija, D. Kainmueller, and B. Savchynskyy,
    “A study of lagrangean decompositions and dual ascent solvers for graph matching,”
    presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA,
    United States, 2017, vol. 2017, pp. 7062–7071.'
  ista: 'Swoboda P, Rother C, Abu Alhaija C, Kainmueller D, Savchynskyy B. 2017. A
    study of lagrangean decompositions and dual ascent solvers for graph matching.
    CVPR: Computer Vision and Pattern Recognition vol. 2017, 7062–7071.'
  mla: Swoboda, Paul, et al. <i>A Study of Lagrangean Decompositions and Dual Ascent
    Solvers for Graph Matching</i>. Vol. 2017, IEEE, 2017, pp. 7062–71, doi:<a href="https://doi.org/10.1109/CVPR.2017.747">10.1109/CVPR.2017.747</a>.
  short: P. Swoboda, C. Rother, C. Abu Alhaija, D. Kainmueller, B. Savchynskyy, in:,
    IEEE, 2017, pp. 7062–7071.
conference:
  end_date: 2017-07-26
  location: Honolulu, HA, United States
  name: 'CVPR: Computer Vision and Pattern Recognition'
  start_date: 2017-07-21
corr_author: '1'
date_created: 2018-12-11T11:49:11Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2024-11-04T13:52:34Z
day: '01'
ddc:
- '000'
department:
- _id: VlKo
doi: 10.1109/CVPR.2017.747
ec_funded: 1
external_id:
  isi:
  - '000418371407018'
file:
- access_level: open_access
  checksum: e38a2740daad1ea178465843b5072906
  content_type: application/pdf
  creator: dernst
  date_created: 2019-01-18T12:49:38Z
  date_updated: 2020-07-14T12:48:15Z
  file_id: '5848'
  file_name: 2017_CVPR_Swoboda2.pdf
  file_size: 944332
  relation: main_file
file_date_updated: 2020-07-14T12:48:15Z
has_accepted_license: '1'
intvolume: '      2017'
isi: 1
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 7062-7071
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '616160'
  name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_identifier:
  isbn:
  - 978-153860457-1
publication_status: published
publisher: IEEE
publist_id: '6525'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A study of lagrangean decompositions and dual ascent solvers for graph matching
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 2017
year: '2017'
...