Home > Research > Publications & Outputs > Binary positive semidefinite matrices and assoc...

Research

Links

Text available via DOI:

View graph of relations

Binary positive semidefinite matrices and associated integer polytopes

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter (peer-reviewed) › peer-review

Published

Standard

Binary positive semidefinite matrices and associated integer polytopes. / Letchford, A N; Sorensen, M M.
Integer Programming and Combinatorial Optimization : Proceedings of the 13th International IPCO Conference. ed. / Andrea Lodi; Alessandro Panconesi; Giovanni Rinaldi. Berlin: Springer, 2008. p. 125-139 (Lecture Notes in Computer Science; Vol. 5035).

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Chapter (peer-reviewed) › peer-review

Harvard

Letchford, AN & Sorensen, MM 2008, Binary positive semidefinite matrices and associated integer polytopes. in A Lodi, A Panconesi & G Rinaldi (eds), Integer Programming and Combinatorial Optimization : Proceedings of the 13th International IPCO Conference. Lecture Notes in Computer Science, vol. 5035, Springer, Berlin, pp. 125-139, 13th International IPCO Conference, Bertinoro, Italy, 26/05/08. https://doi.org/10.1007/978-3-540-68891-4_9

APA

Letchford, A. N., & Sorensen, M. M. (2008). Binary positive semidefinite matrices and associated integer polytopes. In A. Lodi, A. Panconesi, & G. Rinaldi (Eds.), Integer Programming and Combinatorial Optimization : Proceedings of the 13th International IPCO Conference (pp. 125-139). (Lecture Notes in Computer Science; Vol. 5035). Springer. https://doi.org/10.1007/978-3-540-68891-4_9

Vancouver

Letchford AN, Sorensen MM. Binary positive semidefinite matrices and associated integer polytopes. In Lodi A, Panconesi A, Rinaldi G, editors, Integer Programming and Combinatorial Optimization : Proceedings of the 13th International IPCO Conference. Berlin: Springer. 2008. p. 125-139. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-68891-4_9

Author

Letchford, A N ; Sorensen, M M. / Binary positive semidefinite matrices and associated integer polytopes. Integer Programming and Combinatorial Optimization : Proceedings of the 13th International IPCO Conference. editor / Andrea Lodi ; Alessandro Panconesi ; Giovanni Rinaldi. Berlin : Springer, 2008. pp. 125-139 (Lecture Notes in Computer Science).

Bibtex

@inbook{562813dbf75f41c4a2af125337ab1f85,
title = "Binary positive semidefinite matrices and associated integer polytopes",
abstract = "We consider the positive semidefinite (psd) matrices with binary entries. We give a characterisation of such matrices, along with a graphical representation. We then move on to consider the associated integer polytopes. Several important and well-known integer polytopes (the cut, boolean quadric, multicut and clique partitioning polytopes) are shown to arise as projections of binary psd polytopes. Finally, we present various valid inequalities for binary psd polytopes, and show how they relate to inequalities known for the simpler polytopes mentioned. Along the way, we answer an open question in the literature on the max-cut problem, by showing that the so-called k-gonal inequalities define a polytope.",
author = "Letchford, {A N} and Sorensen, {M M}",
note = "The full version of this paper appeared as: A.N. Letchford & M.M. S{\o}rensen (2012) Binary positive semidefinite matrices and associated integer polytopes. Math. Program., 131(1), 253-271.; 13th International IPCO Conference ; Conference date: 26-05-2008 Through 28-05-2008",
year = "2008",
doi = "10.1007/978-3-540-68891-4_9",
language = "English",
isbn = "3540688862",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "125--139",
editor = "Andrea Lodi and Alessandro Panconesi and Giovanni Rinaldi",
booktitle = "Integer Programming and Combinatorial Optimization",

}

RIS

TY - CHAP

T1 - Binary positive semidefinite matrices and associated integer polytopes

AU - Letchford, A N

AU - Sorensen, M M

N1 - The full version of this paper appeared as: A.N. Letchford & M.M. Sørensen (2012) Binary positive semidefinite matrices and associated integer polytopes. Math. Program., 131(1), 253-271.

PY - 2008

Y1 - 2008

N2 - We consider the positive semidefinite (psd) matrices with binary entries. We give a characterisation of such matrices, along with a graphical representation. We then move on to consider the associated integer polytopes. Several important and well-known integer polytopes (the cut, boolean quadric, multicut and clique partitioning polytopes) are shown to arise as projections of binary psd polytopes. Finally, we present various valid inequalities for binary psd polytopes, and show how they relate to inequalities known for the simpler polytopes mentioned. Along the way, we answer an open question in the literature on the max-cut problem, by showing that the so-called k-gonal inequalities define a polytope.

AB - We consider the positive semidefinite (psd) matrices with binary entries. We give a characterisation of such matrices, along with a graphical representation. We then move on to consider the associated integer polytopes. Several important and well-known integer polytopes (the cut, boolean quadric, multicut and clique partitioning polytopes) are shown to arise as projections of binary psd polytopes. Finally, we present various valid inequalities for binary psd polytopes, and show how they relate to inequalities known for the simpler polytopes mentioned. Along the way, we answer an open question in the literature on the max-cut problem, by showing that the so-called k-gonal inequalities define a polytope.

U2 - 10.1007/978-3-540-68891-4_9

DO - 10.1007/978-3-540-68891-4_9

M3 - Chapter (peer-reviewed)

SN - 3540688862

T3 - Lecture Notes in Computer Science

SP - 125

EP - 139

BT - Integer Programming and Combinatorial Optimization

A2 - Lodi, Andrea

A2 - Panconesi, Alessandro

A2 - Rinaldi, Giovanni

PB - Springer

CY - Berlin

T2 - 13th International IPCO Conference

Y2 - 26 May 2008 through 28 May 2008

ER -