<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>34573</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>463</pageFirst>
    <pageLast>490</pageLast>
    <pageNumber>28</pageNumber>
    <edition/>
    <issue>4</issue>
    <volume>42</volume>
    <type>articler</type>
    <publisherName>Springer Science and Business Media LLC</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2024-11-14</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Computing the Covering Radius of a Polytope with an Application to Lonely Runners</title>
    <abstract language="eng">We study the computational problem of determining the covering radius of a rational polytope. This parameter is defined as the minimal dilation factor that is needed for the lattice translates of the correspondingly dilated polytope to cover the whole space. As our main result, we describe a new algorithm for this problem, which is simpler, more efficient and easier to implement than the only prior algorithm of Kannan (1992).&#13;
&#13;
Motivated by a variant of the famous Lonely Runner Conjecture, we use its geometric interpretation in terms of covering radii of zonotopes, and apply our algorithm to prove the first open case of three runners with individual starting points.</abstract>
    <parentTitle language="eng">Combinatorica</parentTitle>
    <identifier type="doi">10.1007/s00493-020-4633-8</identifier>
    <identifier type="issn">0209-9683</identifier>
    <enrichment key="opus_doi_flag">true</enrichment>
    <enrichment key="opus_doi_json">{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,10,4]],"date-time":"2022-10-04T04:53:33Z","timestamp":1664859213800},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,2,18]],"date-time":"2022-02-18T00:00:00Z","timestamp":1645142400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,2,18]],"date-time":"2022-02-18T00:00:00Z","timestamp":1645142400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2022,8]]},"DOI":"10.1007\/s00493-020-4633-8","type":"journal-article","created":{"date-parts":[[2022,2,18]],"date-time":"2022-02-18T11:24:41Z","timestamp":1645183481000},"page":"463-490","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Computing the Covering Radius of a Polytope with an Application to Lonely Runners"],"prefix":"10.1007","volume":"42","author":[{"given":"Jana","family":"Cslovjecsek","sequence":"first","affiliation":[]},{"given":"Romanos Diogenes","family":"Malikiosis","sequence":"additional","affiliation":[]},{"given":"M\u00e1rton","family":"Nasz\u00f3di","sequence":"additional","affiliation":[]},{"given":"Matthias","family":"Schymura","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,18]]},"reference":[{"key":"4633_CR1","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/s10107-015-0865-6","volume":"154","author":"G Averkov","year":"2015","unstructured":"G. Averkov and A. Basu: Lifting properties of maximal lattice-free polyhedra, Math. Program. 154 (2015), 81\u2013111.","journal-title":"Math. Program."},{"key":"4633_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s13366-011-0028-8","volume":"53","author":"G Averkov","year":"2012","unstructured":"G. Averkov and C. Wagner: Inequalities for the lattice width of lattice-free convex sets in the plane, Beitr. Algebra Geom. 53 (2012), 1\u201323.","journal-title":"Beitr. Algebra Geom."},{"key":"4633_CR3","doi-asserted-by":"publisher","first-page":"5687","DOI":"10.1016\/j.disc.2008.04.041","volume":"309","author":"J Barajas","year":"2009","unstructured":"J. Barajas and O. Serra: On the chromatic number of circulant graphs, Discrete Math. 309 (2009), 5687\u20135696.","journal-title":"Discrete Math."},{"key":"4633_CR4","series-title":"Graduate Studies in Mathematics","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/054","volume-title":"A course in convexity","author":"A Barvinok","year":"2002","unstructured":"A. Barvinok: A course in convexity, Graduate Studies in Mathematics, vol. 54, American Mathematical Society, Providence, RI, 2002."},{"key":"4633_CR5","first-page":"#A29","volume":"19","author":"M Beck","year":"2019","unstructured":"M. Beck, S. Ho\u015ften and M. Schymura: Lonely Runner Polyhedra, Integers 19 (2019), #A29.","journal-title":"Integers"},{"key":"4633_CR6","doi-asserted-by":"crossref","unstructured":"T. Bohman, R. Holzman and D. Kleitman: Six lonely runners, Electron. J. Combin. 8 (2001), Research Paper 3, (electronic). In honor of Aviezri Fraenkel on the occasion of his 70th birthday.","DOI":"10.37236\/1602"},{"key":"4633_CR7","doi-asserted-by":"publisher","first-page":"4814","DOI":"10.1016\/j.tcs.2011.02.009","volume":"412","author":"\u00c9 Charrier","year":"2011","unstructured":"\u00c9. Charrier, F. Feschet and L. Buzer: Computing efficiently the lattice width in any dimension, Theoret. Comput. Sci. 412 (2011), 4814\u20134823.","journal-title":"Theoret. Comput. Sci."},{"key":"4633_CR8","doi-asserted-by":"crossref","unstructured":"G. Codenotti, F. Santos and M. Schymura: The covering radius and a discrete surface area for non-hollow simplices, Discrete Comput. Geom. (2021), to appear, https:\/\/arxiv.org\/abs\/1903.02866.","DOI":"10.1007\/s00454-021-00330-3"},{"key":"4633_CR9","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/BF01832623","volume":"9","author":"T W Cusick","year":"1973","unstructured":"Th. W. Cusick: View-obstruction problems, Aequat. Math. 9 (1973), 165\u2013170.","journal-title":"Aequat. Math."},{"key":"4633_CR10","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.ipl.2008.03.019","volume":"108","author":"S Czerwi\u0144ski","year":"2008","unstructured":"S. Czerwi\u0144ski and J. Grytczuk: Invisible runners in finite fields, Inf. Process. Lett. 108 (2008), 64\u201367.","journal-title":"Inf. Process. Lett."},{"key":"4633_CR11","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/s10107-013-0654-z","volume":"145","author":"S Dash","year":"2014","unstructured":"S. Dash, N. B. Dobbs, O. G\u00fcnl\u00fck, T. J. Nowicki and G. M. \u015awirszcz: Latticefree sets, multi-branch split disjunctions, and mixed-integer programming, Math. Program. 145 (2014), 483\u2013508.","journal-title":"Math. Program."},{"key":"4633_CR12","series-title":"North-Holland Mathematical Library","volume-title":"Geometry of Numbers","author":"P M Gruber","year":"1987","unstructured":"P. M. Gruber and C. G. Lekkerkerker: Geometry of Numbers, second ed., North-Holland Mathematical Library, vol. 37, North-Holland Publishing Co., Amsterdam, 1987.","edition":"second ed."},{"key":"4633_CR13","unstructured":"I. Haviv and O. Regev: Hardness of the covering radius problem on lattices, Chic. J. Theoret. Comput. Sci. (2012), Article 4."},{"key":"4633_CR14","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s00010-016-0458-3","volume":"91","author":"M Henze","year":"2017","unstructured":"M. Henze and R.-D. Malikiosis: On the covering radius of lattice zonotopes and its relation to view-obstructions and the lonely runner conjecture, Aequat. Math. 91 (2017), 331\u2013352.","journal-title":"Aequat. Math."},{"key":"4633_CR15","doi-asserted-by":"publisher","first-page":"6605","DOI":"10.1090\/tran\/7531","volume":"371","author":"O Iglesias-Vali\u00f1o","year":"2019","unstructured":"O. Iglesias-Vali\u00f1o and F. Santos: Classification of empty lattice 4-simplices of width larger than two, Trans. Amer. Math. Soc. 371 (2019), 6605\u20136625.","journal-title":"Trans. Amer. Math. Soc."},{"key":"4633_CR16","series-title":"Polyhedral Combinatorics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science","first-page":"39","volume-title":"Test sets for integer programs, \u2200\u2203 sentences","author":"R Kannan","year":"1990","unstructured":"R. Kannan: Test sets for integer programs, \u2200\u2203 sentences, Polyhedral Combinatorics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 1, Providence, RI, American Mathematical Society, 1990, 39\u201347."},{"key":"4633_CR17","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF01204720","volume":"12","author":"R Kannan","year":"1992","unstructured":"R. Kannan: Lattice translates of a polytope and the Frobenius problem, Combinatorica 12 (1992), 161\u2013177.","journal-title":"Combinatorica"},{"key":"4633_CR18","doi-asserted-by":"publisher","first-page":"577","DOI":"10.2307\/1971436","volume":"128","author":"R Kannan","year":"1988","unstructured":"R. Kannan and L. Lov\u00e1sz: Covering minima and lattice-point-free convex bodies, Ann. of Math. (2) 128 (1988), 577\u2013602.","journal-title":"Ann. of Math. (2)"},{"key":"4633_CR19","unstructured":"N. Kravitz: Barely lonely runners and very lonely runners, https:\/\/arxiv.org\/abs\/1912.06034, 2019."},{"key":"4633_CR20","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"H W Lenstra","year":"1983","unstructured":"H. W. Lenstra: Integer programming with a fixed number of variables, Math. Oper. Res. 8 (1983), 538\u2013548.","journal-title":"Math. Oper. Res."},{"key":"4633_CR21","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1137\/0607052","volume":"7","author":"O L Mangasarian","year":"1986","unstructured":"O. L. Mangasarian and T.-H. Shiau: A Variable-Complexity Norm Maximization Problem, SIAM J. Alg. Disc. Meth. 7 (1986), 455\u2013461.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"4633_CR22","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1137\/S0097539703433511","volume":"34","author":"D Micciancio","year":"2004","unstructured":"D. Micciancio: Almost perfect lattices, the covering radius problem, and applications to Ajtai\u2019s connection factor, SIAM J. Comput. 34 (2004), 118\u2013169.","journal-title":"SIAM J. Comput."},{"key":"4633_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0897-7","volume-title":"Complexity of lattice problems. A cryptographic perspective","author":"D Micciancio","year":"2002","unstructured":"D. Micciancio and S. Goldwasser: Complexity of lattice problems. A cryptographic perspective, vol. 671, Boston, MA: Kluwer Academic Publishers, 2002."},{"key":"4633_CR24","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/s10107-018-1323-z","volume":"179","author":"J Paat","year":"2020","unstructured":"J. Paat, R. Weismantel and S. Weltge: Distances between optimal solutions of mixed-integer programs, Math. Program. 179 (2020), 455\u2013468.","journal-title":"Math. Program."},{"key":"4633_CR25","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1023\/A:1009842406728","volume":"4","author":"M Rudelson","year":"2000","unstructured":"M. Rudelson: Distances between non-symmetric convex bodies and the MM*-estimate, Positivity 4 (2000), 161\u2013178.","journal-title":"Positivity"},{"key":"4633_CR26","doi-asserted-by":"crossref","unstructured":"I. J. Schoenberg: Extremum problems for the motions of a billiard ball, II. The L\u221e norm, in: Indag. Math., Nederl. Akad. Wetensch. Proc. Ser. A. 38, 263\u2013279, 1976.","DOI":"10.1016\/1385-7258(76)90053-6"},{"key":"4633_CR27","first-page":"14","volume":"26","author":"M Schymura","year":"2018","unstructured":"M. Schymura and J. M. Wills: Der einsame L\u00e4ufer, Mitt. Dtsch. Math.-Ver. 26 (2018), 14\u201317.","journal-title":"Mitt. Dtsch. Math.-Ver."},{"key":"4633_CR28","first-page":"1","volume":"13","author":"T Tao","year":"2018","unstructured":"T. Tao: Some remarks on the lonely runner conjecture, Contrib. Discrete Math. 13 (2018), 1\u201331.","journal-title":"Contrib. Discrete Math."},{"key":"4633_CR29","unstructured":"The Sage Developers: Sagemath, the Sage Mathematics Software System (Version 9.1), 2020, https:\/\/www.sagemath.org."},{"key":"4633_CR30","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/BF01362551","volume":"72","author":"J M Wills","year":"1968","unstructured":"J. M. Wills: Zur simultanen homogenen diophantischen Approximation. I, Monatsh. Math. 72 (1968), 254\u2013263.","journal-title":"Monatsh. Math."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-020-4633-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-020-4633-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-020-4633-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,3]],"date-time":"2022-10-03T15:04:28Z","timestamp":1664809468000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-020-4633-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,18]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["4633"],"URL":"http:\/\/dx.doi.org\/10.1007\/s00493-020-4633-8","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,18]]},"assertion":[{"value":"5 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}</enrichment>
    <enrichment key="opus_crossrefDocumentType">journal-article</enrichment>
    <enrichment key="opus_crossrefLicence">https://www.springer.com/tdm</enrichment>
    <enrichment key="opus_import_origin">crossref</enrichment>
    <enrichment key="opus_doiImportPopulated">PersonAuthorFirstName_1,PersonAuthorLastName_1,PersonAuthorFirstName_2,PersonAuthorLastName_2,PersonAuthorFirstName_3,PersonAuthorLastName_3,PersonAuthorFirstName_4,PersonAuthorLastName_4,PublisherName,TitleMain_1,Language,TitleParent_1,PageNumber,PageFirst,PageLast,Issue,Volume,PublishedYear,IdentifierIssn,Enrichmentopus_crossrefLicence</enrichment>
    <enrichment key="BTU">an der BTU erstellt / created at BTU</enrichment>
    <enrichment key="Referiert">Beitrag ist referiert / Article peer-reviewed</enrichment>
    <enrichment key="Publikationsweg">Open Access</enrichment>
    <enrichment key="opus.source">doi-import</enrichment>
    <enrichment key="Fprofil">4 Künstliche Intelligenz und Sensorik / Artificial Intelligence and Sensor Technology</enrichment>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">false</enrichment>
    <author>
      <firstName>Jana</firstName>
      <lastName>Cslovjecsek</lastName>
    </author>
    <submitter>
      <firstName>Matthias</firstName>
      <lastName>Schymura</lastName>
    </submitter>
    <author>
      <firstName>Romanos Diogenes</firstName>
      <lastName>Malikiosis</lastName>
    </author>
    <author>
      <firstName>Márton</firstName>
      <lastName>Naszódi</lastName>
    </author>
    <author>
      <firstName>Matthias</firstName>
      <lastName>Schymura</lastName>
    </author>
    <collection role="institutes" number="1302">FG Algorithmische Mathematik</collection>
  </doc>
</export-example>
