An Online Algorithm for the Postman Problem with a Small Penalty View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2001-08-17

AUTHORS

Piotr Berman , Junichiro Fukuyama

ABSTRACT

The Postman Problem is defined in the following manner: Given a connected graph G and a start point s τ V(G), we call a path J in G a postman tour if J starts and ends at s and contains every edge in E(G). We want to find a shortest postman tour in G. Thus, we minimize the number |J| - |E(G)|, called the penalty of J for G. In this paper, we consider two online versions of The Postman Problem, in which the postman is initially placed at a start point and allowed to move on edges. The postman is given information on the incident edges and/or the adjacent vertices of the current vertex v. The first model is called The Labyrinth Model, where the postman only knows the existence of the incident edges from v. Thus, he/she does not know the other endpoint w of an edge from v, even if it is already visited. The second one is The Corridor Model, where the postman can ‘see’ the other endpoint w from v. This means that if w is already visited, he/she knows the existence of w before traversing the edge (v,w). We devised an algorithm for The Corridor Model whose penalty is bounded by 2| V(G)| - 2. It performs better than the algorithm described in [8], in the case when the other visited endpoint of an edge from a current vertex is known to the postman. In addition, we obtained lower bounds of a penalty for The Corridor and Labyrinth Models. They are (4|V(G)|-5)/3 and (5|V(G)| -3)/4, respectively. Our online algorithm uses a linear time algorithm for the offline Postman Problem with a penalty at most |V| - 1. Thus, the minimum penalty does not exceed |V| - 1 for every connected graph G. This is the first known upper bound of a penalty of an offline postman tour, and matches the obvious lower bound exactly. More... »

PAGES

48-54

Book

TITLE

Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques

ISBN

978-3-540-42470-3
978-3-540-44666-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44666-4_9

DOI

http://dx.doi.org/10.1007/3-540-44666-4_9

DIMENSIONS

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


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": "Department of Computer Science and Engineering, The Pennsylvania State University, 16802, University Park, PA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, The Pennsylvania State University, 16802, University Park, PA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, The Pennsylvania State University, 16802, University Park, PA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, The Pennsylvania State University, 16802, University Park, PA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fukuyama", 
        "givenName": "Junichiro", 
        "id": "sg:person.015266205731.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015266205731.31"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2001-08-17", 
    "datePublishedReg": "2001-08-17", 
    "description": "The Postman Problem is defined in the following manner: Given a connected graph G and a start point s \u03c4 V(G), we call a path J in G a postman tour if J starts and ends at s and contains every edge in E(G). We want to find a shortest postman tour in G. Thus, we minimize the number |J| - |E(G)|, called the penalty of J for G. In this paper, we consider two online versions of The Postman Problem, in which the postman is initially placed at a start point and allowed to move on edges. The postman is given information on the incident edges and/or the adjacent vertices of the current vertex v. The first model is called The Labyrinth Model, where the postman only knows the existence of the incident edges from v. Thus, he/she does not know the other endpoint w of an edge from v, even if it is already visited. The second one is The Corridor Model, where the postman can \u2018see\u2019 the other endpoint w from v. This means that if w is already visited, he/she knows the existence of w before traversing the edge (v,w). We devised an algorithm for The Corridor Model whose penalty is bounded by 2| V(G)| - 2. It performs better than the algorithm described in [8], in the case when the other visited endpoint of an edge from a current vertex is known to the postman. In addition, we obtained lower bounds of a penalty for The Corridor and Labyrinth Models. They are (4|V(G)|-5)/3 and (5|V(G)| -3)/4, respectively. Our online algorithm uses a linear time algorithm for the offline Postman Problem with a penalty at most |V| - 1. Thus, the minimum penalty does not exceed |V| - 1 for every connected graph G. This is the first known upper bound of a penalty of an offline postman tour, and matches the obvious lower bound exactly.", 
    "editor": [
      {
        "familyName": "Goemans", 
        "givenName": "Michel", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9 D. P.", 
        "type": "Person"
      }, 
      {
        "familyName": "Trevisan", 
        "givenName": "Luca", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44666-4_9", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42470-3", 
        "978-3-540-44666-8"
      ], 
      "name": "Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques", 
      "type": "Book"
    }, 
    "keywords": [
      "postman problem", 
      "postman tour", 
      "linear time algorithm", 
      "shortest postman tour", 
      "online algorithm", 
      "lower bounds", 
      "current vertex", 
      "graph G.", 
      "adjacent vertices", 
      "connected graph G", 
      "graph G", 
      "incident edges", 
      "time algorithm", 
      "corridor model", 
      "connected graph G.", 
      "vertex v.", 
      "first model", 
      "algorithm", 
      "vertices", 
      "problem", 
      "second one", 
      "small penalty", 
      "existence", 
      "bounds", 
      "edge", 
      "model", 
      "minimum penalty", 
      "penalty", 
      "G.", 
      "version", 
      "following manner", 
      "point", 
      "one", 
      "start point", 
      "number", 
      "Postman", 
      "cases", 
      "tour", 
      "online version", 
      "information", 
      "incidents", 
      "manner", 
      "v.", 
      "corridor", 
      "addition", 
      "endpoint", 
      "paper"
    ], 
    "name": "An Online Algorithm for the Postman Problem with a Small Penalty", 
    "pagination": "48-54", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011915729"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44666-4_9"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44666-4_9", 
      "https://app.dimensions.ai/details/publication/pub.1011915729"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:22", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_452.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44666-4_9"
  }
]
 

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/3-540-44666-4_9'

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/3-540-44666-4_9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44666-4_9'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-44666-4_9'


 

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

128 TRIPLES      22 PREDICATES      71 URIs      64 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44666-4_9 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Ne20b93edd4e84c23a4fa63e717697f88
4 schema:datePublished 2001-08-17
5 schema:datePublishedReg 2001-08-17
6 schema:description The Postman Problem is defined in the following manner: Given a connected graph G and a start point s τ V(G), we call a path J in G a postman tour if J starts and ends at s and contains every edge in E(G). We want to find a shortest postman tour in G. Thus, we minimize the number |J| - |E(G)|, called the penalty of J for G. In this paper, we consider two online versions of The Postman Problem, in which the postman is initially placed at a start point and allowed to move on edges. The postman is given information on the incident edges and/or the adjacent vertices of the current vertex v. The first model is called The Labyrinth Model, where the postman only knows the existence of the incident edges from v. Thus, he/she does not know the other endpoint w of an edge from v, even if it is already visited. The second one is The Corridor Model, where the postman can ‘see’ the other endpoint w from v. This means that if w is already visited, he/she knows the existence of w before traversing the edge (v,w). We devised an algorithm for The Corridor Model whose penalty is bounded by 2| V(G)| - 2. It performs better than the algorithm described in [8], in the case when the other visited endpoint of an edge from a current vertex is known to the postman. In addition, we obtained lower bounds of a penalty for The Corridor and Labyrinth Models. They are (4|V(G)|-5)/3 and (5|V(G)| -3)/4, respectively. Our online algorithm uses a linear time algorithm for the offline Postman Problem with a penalty at most |V| - 1. Thus, the minimum penalty does not exceed |V| - 1 for every connected graph G. This is the first known upper bound of a penalty of an offline postman tour, and matches the obvious lower bound exactly.
7 schema:editor N8c503d9e9fd142c189eac2702b18ecf9
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Ne22dfb84c2084c1498ceef03df65de8e
11 schema:keywords G.
12 Postman
13 addition
14 adjacent vertices
15 algorithm
16 bounds
17 cases
18 connected graph G
19 connected graph G.
20 corridor
21 corridor model
22 current vertex
23 edge
24 endpoint
25 existence
26 first model
27 following manner
28 graph G
29 graph G.
30 incident edges
31 incidents
32 information
33 linear time algorithm
34 lower bounds
35 manner
36 minimum penalty
37 model
38 number
39 one
40 online algorithm
41 online version
42 paper
43 penalty
44 point
45 postman problem
46 postman tour
47 problem
48 second one
49 shortest postman tour
50 small penalty
51 start point
52 time algorithm
53 tour
54 v.
55 version
56 vertex v.
57 vertices
58 schema:name An Online Algorithm for the Postman Problem with a Small Penalty
59 schema:pagination 48-54
60 schema:productId N812c9b966680419c897cf6585b1c53a1
61 N9b806cd48c0f49dab063a891ff01a605
62 schema:publisher Nebf8650ec46f43789d13ded55853e332
63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011915729
64 https://doi.org/10.1007/3-540-44666-4_9
65 schema:sdDatePublished 2022-08-04T17:22
66 schema:sdLicense https://scigraph.springernature.com/explorer/license/
67 schema:sdPublisher N0dec326a6d094ff99ee4922cf6368318
68 schema:url https://doi.org/10.1007/3-540-44666-4_9
69 sgo:license sg:explorer/license/
70 sgo:sdDataset chapters
71 rdf:type schema:Chapter
72 N02e1b45be11444c39ac7e77e67e99d0c schema:familyName Rolim
73 schema:givenName José D. P.
74 rdf:type schema:Person
75 N0dec326a6d094ff99ee4922cf6368318 schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 N5b064c8ddc5b4f8aad823a3e99482b8b rdf:first sg:person.015266205731.31
78 rdf:rest rdf:nil
79 N5d052a90d7994f48b4200062a5713ccb rdf:first N5da041de8f26428dade162866b11dc34
80 rdf:rest rdf:nil
81 N5da041de8f26428dade162866b11dc34 schema:familyName Trevisan
82 schema:givenName Luca
83 rdf:type schema:Person
84 N812c9b966680419c897cf6585b1c53a1 schema:name dimensions_id
85 schema:value pub.1011915729
86 rdf:type schema:PropertyValue
87 N8c503d9e9fd142c189eac2702b18ecf9 rdf:first Nb0683278f9fc45f5ae81dc74fd168ebb
88 rdf:rest Na9bf9024e65e4e21865af8ed2658fe6f
89 N9b806cd48c0f49dab063a891ff01a605 schema:name doi
90 schema:value 10.1007/3-540-44666-4_9
91 rdf:type schema:PropertyValue
92 N9dffb3e334ed4c2ca7c704296d1723b0 schema:familyName Jansen
93 schema:givenName Klaus
94 rdf:type schema:Person
95 N9e800e2c0b2c4b348a693a7e4645b869 rdf:first N02e1b45be11444c39ac7e77e67e99d0c
96 rdf:rest N5d052a90d7994f48b4200062a5713ccb
97 Na9bf9024e65e4e21865af8ed2658fe6f rdf:first N9dffb3e334ed4c2ca7c704296d1723b0
98 rdf:rest N9e800e2c0b2c4b348a693a7e4645b869
99 Nb0683278f9fc45f5ae81dc74fd168ebb schema:familyName Goemans
100 schema:givenName Michel
101 rdf:type schema:Person
102 Ne20b93edd4e84c23a4fa63e717697f88 rdf:first sg:person.01274506210.27
103 rdf:rest N5b064c8ddc5b4f8aad823a3e99482b8b
104 Ne22dfb84c2084c1498ceef03df65de8e schema:isbn 978-3-540-42470-3
105 978-3-540-44666-8
106 schema:name Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques
107 rdf:type schema:Book
108 Nebf8650ec46f43789d13ded55853e332 schema:name Springer Nature
109 rdf:type schema:Organisation
110 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
111 schema:name Mathematical Sciences
112 rdf:type schema:DefinedTerm
113 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
114 schema:name Pure Mathematics
115 rdf:type schema:DefinedTerm
116 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
117 schema:familyName Berman
118 schema:givenName Piotr
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
120 rdf:type schema:Person
121 sg:person.015266205731.31 schema:affiliation grid-institutes:grid.29857.31
122 schema:familyName Fukuyama
123 schema:givenName Junichiro
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015266205731.31
125 rdf:type schema:Person
126 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science and Engineering, The Pennsylvania State University, 16802, University Park, PA
127 schema:name Department of Computer Science and Engineering, The Pennsylvania State University, 16802, University Park, PA
128 rdf:type schema:Organization
 




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


...