Permutation codes:  a branch and bound approach

Roberto Montemanni; Janos Barta; Derek H. Smith

Permutation codes: a branch and bound approach

Roberto Montemanni, Janos Barta, Derek H. Smith

Faculty of Computing, Engineering and Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

This paper presents a new approach for retrieving
largest possible permutation codes. These have applications in
error correction for telecommunication purposes. The method
presented is based on combinatorial optimization concepts such
as branch and bound techniques and incorporates new adhoc
theoretical results. It is shown how the method can be
applied to obtain new results for subproblems. These results for
subproblems can be combined with other theoretical results to
obtain new results for complete instances. It is shown how the
new improved upper bound M(7,5) ≤ 124 can be obtained with
such techniques.

Original language	English
Title of host publication	ADVANCES in APPLIED and PURE MATHEMATICS
Subtitle of host publication	Proceedings of the 2014 International Conference on Pure Mathematics, Applied Mathematics, Computational Methods (PMAMCM 2014)
Pages	86-90
Number of pages	4
Publication status	Published - 17 Jul 2014
Event	2014 International Conference on Pure Mathematics, Applied Mathematics, Computational Methods - Santorini Island, Greece Duration: 17 Jul 2014 → 21 Jul 2014

Publication series

Name	Mathematics and Computers in Science and Engineering Series
Volume	29
ISSN (Print)	2227-4588

Conference

Conference	2014 International Conference on Pure Mathematics, Applied Mathematics, Computational Methods
Abbreviated title	PMAMCM 2014
Country/Territory	Greece
City	Santorini Island
Period	17/07/14 → 21/07/14

Keywords

permutation codes
Branch and bound algorithms
Upper bounds

Access to Document

Cite this

Montemanni, R., Barta, J., & Smith, D. H. (2014). Permutation codes: a branch and bound approach. In ADVANCES in APPLIED and PURE MATHEMATICS: Proceedings of the 2014 International Conference on Pure Mathematics, Applied Mathematics, Computational Methods (PMAMCM 2014) (pp. 86-90). (Mathematics and Computers in Science and Engineering Series; Vol. 29). http://reswin1.isd.glam.ac.uk/f/3135/Smith-Permutationcodes-2014.pdf

@inproceedings{cb2e5f393a9f4d809363070a8f370b47,

title = "Permutation codes: a branch and bound approach",

abstract = "This paper presents a new approach for retrievinglargest possible permutation codes. These have applications inerror correction for telecommunication purposes. The methodpresented is based on combinatorial optimization concepts suchas branch and bound techniques and incorporates new adhoctheoretical results. It is shown how the method can beapplied to obtain new results for subproblems. These results forsubproblems can be combined with other theoretical results toobtain new results for complete instances. It is shown how thenew improved upper bound M(7,5) ≤ 124 can be obtained withsuch techniques.",

keywords = "permutation codes, Branch and bound algorithms, Upper bounds",

author = "Roberto Montemanni and Janos Barta and Smith, {Derek H.}",

year = "2014",

month = jul,

day = "17",

language = "English",

isbn = "978-1-61804-240-8 ",

series = "Mathematics and Computers in Science and Engineering Series",

pages = "86--90",

booktitle = "ADVANCES in APPLIED and PURE MATHEMATICS",

note = "2014 International Conference on Pure Mathematics, Applied Mathematics, Computational Methods, PMAMCM 2014 ; Conference date: 17-07-2014 Through 21-07-2014",

}

Montemanni, R, Barta, J & Smith, DH 2014, Permutation codes: a branch and bound approach. in ADVANCES in APPLIED and PURE MATHEMATICS: Proceedings of the 2014 International Conference on Pure Mathematics, Applied Mathematics, Computational Methods (PMAMCM 2014). Mathematics and Computers in Science and Engineering Series, vol. 29, pp. 86-90, 2014 International Conference on Pure Mathematics, Applied Mathematics, Computational Methods, Santorini Island, Greece, 17/07/14. <http://reswin1.isd.glam.ac.uk/f/3135/Smith-Permutationcodes-2014.pdf>

Permutation codes: a branch and bound approach. / Montemanni, Roberto; Barta, Janos; Smith, Derek H.
ADVANCES in APPLIED and PURE MATHEMATICS: Proceedings of the 2014 International Conference on Pure Mathematics, Applied Mathematics, Computational Methods (PMAMCM 2014). 2014. p. 86-90 (Mathematics and Computers in Science and Engineering Series; Vol. 29).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Permutation codes

T2 - 2014 International Conference on Pure Mathematics, Applied Mathematics, Computational Methods

AU - Montemanni, Roberto

AU - Barta, Janos

AU - Smith, Derek H.

PY - 2014/7/17

Y1 - 2014/7/17

N2 - This paper presents a new approach for retrievinglargest possible permutation codes. These have applications inerror correction for telecommunication purposes. The methodpresented is based on combinatorial optimization concepts suchas branch and bound techniques and incorporates new adhoctheoretical results. It is shown how the method can beapplied to obtain new results for subproblems. These results forsubproblems can be combined with other theoretical results toobtain new results for complete instances. It is shown how thenew improved upper bound M(7,5) ≤ 124 can be obtained withsuch techniques.

AB - This paper presents a new approach for retrievinglargest possible permutation codes. These have applications inerror correction for telecommunication purposes. The methodpresented is based on combinatorial optimization concepts suchas branch and bound techniques and incorporates new adhoctheoretical results. It is shown how the method can beapplied to obtain new results for subproblems. These results forsubproblems can be combined with other theoretical results toobtain new results for complete instances. It is shown how thenew improved upper bound M(7,5) ≤ 124 can be obtained withsuch techniques.

KW - permutation codes

KW - Branch and bound algorithms

KW - Upper bounds

M3 - Conference contribution

SN - 978-1-61804-240-8

T3 - Mathematics and Computers in Science and Engineering Series

SP - 86

EP - 90

BT - ADVANCES in APPLIED and PURE MATHEMATICS

Y2 - 17 July 2014 through 21 July 2014

ER -