Computing the crosscap number of a knot using integer programming and normal surfaces

Burton, B and Ozlen, M 2012, 'Computing the crosscap number of a knot using integer programming and normal surfaces', ACM Transactions on Mathematical Software, vol. 39, no. 1, 4, pp. 1-18.

Document type: Journal Article
Collection: Journal Articles

Attached Files
Name Description MIMEType Size
n2006038490.pdf Accepted Manuscript application/pdf 341.64KB
Title Computing the crosscap number of a knot using integer programming and normal surfaces
Author(s) Burton, B
Ozlen, M
Year 2012
Journal name ACM Transactions on Mathematical Software
Volume number 39
Issue number 1
Article Number 4
Start page 1
End page 18
Total pages 18
Publisher Association for Computing Machinery, Inc.
Abstract The crosscap number of a knot is an invariant describing the non-orientable surface of smallest genus that the knot bounds. Unlike knot genus (its orientable counterpart), crosscap numbers are difficult to compute and no general algorithm is known. We present three methods for computing crosscap number that offer varying trade-offs between precision and speed: (i) an algorithm based on Hilbert basis enumeration and (ii) an algorithm based on exact integer programming, both of which either compute the solution precisely or reduce it to two possible values, and (iii) a fast but limited precision integer programming algorithm that bounds the solution from above. The first two algorithms advance the theoretical state of the art, but remain intractable for practical use. The third algorithm is fast and effective, which we show in a practical setting by making significant improvements to the current knowledge of crosscap numbers in knot tables. Our integer programming framework is general, with the potential for further applications in computational geometry and topology.
Subject Mathematical Software
Operations Research
Keyword(s) Crosscap number
integer programming
knot genus
knot theory
normal surfaces
DOI - identifier 10.1145/2382585.2382589
Copyright notice © 2012 ACM
ISSN 0098-3500
Additional Notes © ACM 2012. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in, ACM Transactions on Mathematical Software
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 9 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 0 times in Scopus Article
Altmetric details:
Access Statistics: 115 Abstract Views, 12 File Downloads  -  Detailed Statistics
Created: Mon, 07 Jan 2013, 09:08:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us