Journal article icon

Journal article

Large-scale binary quadratic optimization using semidefinite relaxation and applications

Abstract:

In computer vision, many problems can be formulated as binary quadratic programs (BQPs), which are in general NP hard. Finding a solution when the problem is of large size to be of practical interest typically requires relaxation. Semidefinite relaxation usually yields tight bounds, but its computational complexity is high. In this work, we present a semidefinite programming (SDP) formulation for BQPs, with two desirable properties. First, it produces similar bounds to the standard SDP formul...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1109/tpami.2016.2541146

Authors


More by this author
Role:
Author
ORCID:
0000-0002-8648-8718
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Engineering Science
Role:
Author
More from this funder
Name:
Engineering and Physical Sciences Research Council
Grant:
EP/N019474/1
More from this funder
Name:
European Commission
Grant:
321162
More from this funder
Name:
Engineering & Physical Sciences Research Council
Grant:
EP/I001107/2
EP/N019474/1
Publisher:
IEEE
Journal:
IEEE Transactions on Pattern Analysis and Machine Intelligence More from this journal
Volume:
39
Issue:
3
Pages:
470-485
Publication date:
2016-03-11
Acceptance date:
2016-02-22
DOI:
EISSN:
1939-3539
ISSN:
0162-8828
Pmid:
26978557
Language:
English
Keywords:
Pubs id:
pubs:683722
UUID:
uuid:0bae57c9-c5d3-4b8b-b39f-83b5c0fd4423
Local pid:
pubs:683722
Source identifiers:
683722
Deposit date:
2019-03-04

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP