Computing the Covering Radius of a Polytope with an Application to Lonely Runners View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2022-02-18

AUTHORS

Jana Cslovjecsek, Romanos Diogenes Malikiosis, Márton Naszódi, Matthias Schymura

ABSTRACT

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).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. More... »

PAGES

1-28

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00493-020-4633-8

DOI

http://dx.doi.org/10.1007/s00493-020-4633-8

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1145698745


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institute for Mathematics, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, Lausanne, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5333.6", 
          "name": [
            "Institute for Mathematics, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, Lausanne, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Cslovjecsek", 
        "givenName": "Jana", 
        "id": "sg:person.07456730137.40", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07456730137.40"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, Aristotle University of Thessaloniki, Thessaloniki, Greece", 
          "id": "http://www.grid.ac/institutes/grid.4793.9", 
          "name": [
            "Department of Mathematics, Aristotle University of Thessaloniki, Thessaloniki, Greece"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Malikiosis", 
        "givenName": "Romanos Diogenes", 
        "id": "sg:person.013315503475.79", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013315503475.79"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Geometry, Lor\u00e1nd E\u00f6tv\u00f6s University, Budapest, Hungary", 
          "id": "http://www.grid.ac/institutes/grid.5591.8", 
          "name": [
            "Alfr\u00e9d R\u00e9nyi Institute of Mathematics MTA-ELTE Lend\u00fclet, Combinatorial Geometry Research Group, Budapest, Hungary", 
            "Department of Geometry, Lor\u00e1nd E\u00f6tv\u00f6s University, Budapest, Hungary"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nasz\u00f3di", 
        "givenName": "M\u00e1rton", 
        "id": "sg:person.010516374153.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010516374153.52"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Mathematik, BTU Cottbus-Senftenberg, Platz der Deutschen Einheit 1, D-03046, Cottbus, Germany", 
          "id": "http://www.grid.ac/institutes/grid.8842.6", 
          "name": [
            "Institut f\u00fcr Mathematik, BTU Cottbus-Senftenberg, Platz der Deutschen Einheit 1, D-03046, Cottbus, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schymura", 
        "givenName": "Matthias", 
        "id": "sg:person.010211167133.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010211167133.31"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/s00454-021-00330-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1142662670", 
          "https://doi.org/10.1007/s00454-021-00330-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01832623", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016944260", 
          "https://doi.org/10.1007/bf01832623"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s13366-011-0028-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044498519", 
          "https://doi.org/10.1007/s13366-011-0028-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01362551", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046918606", 
          "https://doi.org/10.1007/bf01362551"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01204720", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032674786", 
          "https://doi.org/10.1007/bf01204720"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1009842406728", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001424416", 
          "https://doi.org/10.1023/a:1009842406728"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00010-016-0458-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043992461", 
          "https://doi.org/10.1007/s00010-016-0458-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-013-0654-z", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027954922", 
          "https://doi.org/10.1007/s10107-013-0654-z"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4615-0897-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027648934", 
          "https://doi.org/10.1007/978-1-4615-0897-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-015-0865-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053587689", 
          "https://doi.org/10.1007/s10107-015-0865-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-018-1323-z", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1106281109", 
          "https://doi.org/10.1007/s10107-018-1323-z"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2022-02-18", 
    "datePublishedReg": "2022-02-18", 
    "description": "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).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.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00493-020-4633-8", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1136493", 
        "issn": [
          "0209-9683", 
          "1439-6912"
        ], 
        "name": "Combinatorica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }
    ], 
    "keywords": [
      "covering radius", 
      "geometric interpretation", 
      "first open case", 
      "whole space", 
      "computational problems", 
      "lattice translates", 
      "lonely runner conjecture", 
      "polytope", 
      "rational polytopes", 
      "new algorithm", 
      "main results", 
      "prior algorithms", 
      "algorithm", 
      "dilation factor", 
      "problem", 
      "zonotopes", 
      "open cases", 
      "radius", 
      "Kannan", 
      "conjecture", 
      "space", 
      "parameters", 
      "terms", 
      "point", 
      "applications", 
      "runners", 
      "interpretation", 
      "results", 
      "cases", 
      "translates", 
      "factors", 
      "variants"
    ], 
    "name": "Computing the Covering Radius of a Polytope with an Application to Lonely Runners", 
    "pagination": "1-28", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1145698745"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00493-020-4633-8"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00493-020-4633-8", 
      "https://app.dimensions.ai/details/publication/pub.1145698745"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-10-01T06:51", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_948.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00493-020-4633-8"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00493-020-4633-8'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00493-020-4633-8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-020-4633-8'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00493-020-4633-8'


 

This table displays all metadata directly associated to this object as RDF triples.

158 TRIPLES      21 PREDICATES      65 URIs      46 LITERALS      4 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00493-020-4633-8 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N1ea12c7659fe4af3945e59cf4ecfa482
4 schema:citation sg:pub.10.1007/978-1-4615-0897-7
5 sg:pub.10.1007/bf01204720
6 sg:pub.10.1007/bf01362551
7 sg:pub.10.1007/bf01832623
8 sg:pub.10.1007/s00010-016-0458-3
9 sg:pub.10.1007/s00454-021-00330-3
10 sg:pub.10.1007/s10107-013-0654-z
11 sg:pub.10.1007/s10107-015-0865-6
12 sg:pub.10.1007/s10107-018-1323-z
13 sg:pub.10.1007/s13366-011-0028-8
14 sg:pub.10.1023/a:1009842406728
15 schema:datePublished 2022-02-18
16 schema:datePublishedReg 2022-02-18
17 schema:description 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).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.
18 schema:genre article
19 schema:isAccessibleForFree true
20 schema:isPartOf sg:journal.1136493
21 schema:keywords Kannan
22 algorithm
23 applications
24 cases
25 computational problems
26 conjecture
27 covering radius
28 dilation factor
29 factors
30 first open case
31 geometric interpretation
32 interpretation
33 lattice translates
34 lonely runner conjecture
35 main results
36 new algorithm
37 open cases
38 parameters
39 point
40 polytope
41 prior algorithms
42 problem
43 radius
44 rational polytopes
45 results
46 runners
47 space
48 terms
49 translates
50 variants
51 whole space
52 zonotopes
53 schema:name Computing the Covering Radius of a Polytope with an Application to Lonely Runners
54 schema:pagination 1-28
55 schema:productId N3abdcb82bbe84d0687c475cef7cc63b1
56 N3ec93b65a41142d198a55cd579ce4201
57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1145698745
58 https://doi.org/10.1007/s00493-020-4633-8
59 schema:sdDatePublished 2022-10-01T06:51
60 schema:sdLicense https://scigraph.springernature.com/explorer/license/
61 schema:sdPublisher Nfa57028413fc40e29e9a62f1e9d60823
62 schema:url https://doi.org/10.1007/s00493-020-4633-8
63 sgo:license sg:explorer/license/
64 sgo:sdDataset articles
65 rdf:type schema:ScholarlyArticle
66 N13fa1fcaaa6049098aeb512ba0c1ca82 rdf:first sg:person.010211167133.31
67 rdf:rest rdf:nil
68 N1ea12c7659fe4af3945e59cf4ecfa482 rdf:first sg:person.07456730137.40
69 rdf:rest N4f3bc6adc801437bb24c1e15a61d7883
70 N3abdcb82bbe84d0687c475cef7cc63b1 schema:name doi
71 schema:value 10.1007/s00493-020-4633-8
72 rdf:type schema:PropertyValue
73 N3ec93b65a41142d198a55cd579ce4201 schema:name dimensions_id
74 schema:value pub.1145698745
75 rdf:type schema:PropertyValue
76 N4f3bc6adc801437bb24c1e15a61d7883 rdf:first sg:person.013315503475.79
77 rdf:rest N732d656f03634fffa67303df58b42a5c
78 N732d656f03634fffa67303df58b42a5c rdf:first sg:person.010516374153.52
79 rdf:rest N13fa1fcaaa6049098aeb512ba0c1ca82
80 Nfa57028413fc40e29e9a62f1e9d60823 schema:name Springer Nature - SN SciGraph project
81 rdf:type schema:Organization
82 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
83 schema:name Mathematical Sciences
84 rdf:type schema:DefinedTerm
85 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
86 schema:name Pure Mathematics
87 rdf:type schema:DefinedTerm
88 sg:journal.1136493 schema:issn 0209-9683
89 1439-6912
90 schema:name Combinatorica
91 schema:publisher Springer Nature
92 rdf:type schema:Periodical
93 sg:person.010211167133.31 schema:affiliation grid-institutes:grid.8842.6
94 schema:familyName Schymura
95 schema:givenName Matthias
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010211167133.31
97 rdf:type schema:Person
98 sg:person.010516374153.52 schema:affiliation grid-institutes:grid.5591.8
99 schema:familyName Naszódi
100 schema:givenName Márton
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010516374153.52
102 rdf:type schema:Person
103 sg:person.013315503475.79 schema:affiliation grid-institutes:grid.4793.9
104 schema:familyName Malikiosis
105 schema:givenName Romanos Diogenes
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013315503475.79
107 rdf:type schema:Person
108 sg:person.07456730137.40 schema:affiliation grid-institutes:grid.5333.6
109 schema:familyName Cslovjecsek
110 schema:givenName Jana
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07456730137.40
112 rdf:type schema:Person
113 sg:pub.10.1007/978-1-4615-0897-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027648934
114 https://doi.org/10.1007/978-1-4615-0897-7
115 rdf:type schema:CreativeWork
116 sg:pub.10.1007/bf01204720 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032674786
117 https://doi.org/10.1007/bf01204720
118 rdf:type schema:CreativeWork
119 sg:pub.10.1007/bf01362551 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046918606
120 https://doi.org/10.1007/bf01362551
121 rdf:type schema:CreativeWork
122 sg:pub.10.1007/bf01832623 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016944260
123 https://doi.org/10.1007/bf01832623
124 rdf:type schema:CreativeWork
125 sg:pub.10.1007/s00010-016-0458-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043992461
126 https://doi.org/10.1007/s00010-016-0458-3
127 rdf:type schema:CreativeWork
128 sg:pub.10.1007/s00454-021-00330-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1142662670
129 https://doi.org/10.1007/s00454-021-00330-3
130 rdf:type schema:CreativeWork
131 sg:pub.10.1007/s10107-013-0654-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1027954922
132 https://doi.org/10.1007/s10107-013-0654-z
133 rdf:type schema:CreativeWork
134 sg:pub.10.1007/s10107-015-0865-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053587689
135 https://doi.org/10.1007/s10107-015-0865-6
136 rdf:type schema:CreativeWork
137 sg:pub.10.1007/s10107-018-1323-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1106281109
138 https://doi.org/10.1007/s10107-018-1323-z
139 rdf:type schema:CreativeWork
140 sg:pub.10.1007/s13366-011-0028-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044498519
141 https://doi.org/10.1007/s13366-011-0028-8
142 rdf:type schema:CreativeWork
143 sg:pub.10.1023/a:1009842406728 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001424416
144 https://doi.org/10.1023/a:1009842406728
145 rdf:type schema:CreativeWork
146 grid-institutes:grid.4793.9 schema:alternateName Department of Mathematics, Aristotle University of Thessaloniki, Thessaloniki, Greece
147 schema:name Department of Mathematics, Aristotle University of Thessaloniki, Thessaloniki, Greece
148 rdf:type schema:Organization
149 grid-institutes:grid.5333.6 schema:alternateName Institute for Mathematics, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
150 schema:name Institute for Mathematics, École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
151 rdf:type schema:Organization
152 grid-institutes:grid.5591.8 schema:alternateName Department of Geometry, Loránd Eötvös University, Budapest, Hungary
153 schema:name Alfréd Rényi Institute of Mathematics MTA-ELTE Lendület, Combinatorial Geometry Research Group, Budapest, Hungary
154 Department of Geometry, Loránd Eötvös University, Budapest, Hungary
155 rdf:type schema:Organization
156 grid-institutes:grid.8842.6 schema:alternateName Institut für Mathematik, BTU Cottbus-Senftenberg, Platz der Deutschen Einheit 1, D-03046, Cottbus, Germany
157 schema:name Institut für Mathematik, BTU Cottbus-Senftenberg, Platz der Deutschen Einheit 1, D-03046, Cottbus, Germany
158 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...