An improved approximation ratio for the minimum latency problem View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1998-06

AUTHORS

Michel Goemans, Jon Kleinberg

ABSTRACT

Given a tour visitingn points in a metric space, thelatency of one of these pointsp is the distance traveled in the tour before reachingp. Theminimum latency problem (MLP) asks for a tour passing throughn given points for which the total latency of then points is minimum; in effect, we are seeking the tour with minimum average “arrival time”. This problem has been studied in the operations research literature, where it has also been termed the “delivery-man problem” and the “traveling repairman problem”. The approximability of the MLP was first considered by Sahni and Gonzalez in 1976; however, unlike the classical traveling salesman problem (TSP), it is not easy to give any constant-factor approximation algorithm for the MLP. Recently, Blum et al. (A. Blum, P. Chalasani, D. Coppersimith, W. Pulleyblank, P. Raghavan, M. Sudan, Proceedings of the 26th ACM Symposium on the Theory of Computing, 1994, pp. 163–171) gave the first such algorithm, obtaining an approximation ratio of 144. In this work, we develop an algorithm which improves this ratio to 21.55; moreover, combining our algorithm with a recent result of Garg (N. Garg, Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, 1996, pp. 302–309) provides an approximation ratio of 10.78. The development of our algorithm involves a number of techniques that seem to be of interest from the perspective of the TSP and its variants more generally. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V. More... »

PAGES

111-124

References to SciGraph publications

  • 1980. Heuristic analysis, linear programming and branch and bound in COMBINATORIAL OPTIMIZATION II
  • 1993-03. A note on the prize collecting traveling salesman problem in MATHEMATICAL PROGRAMMING
  • 1989-12. The delivery man problem on a tree network in ANNALS OF OPERATIONS RESEARCH
  • 1993-06. Survivable networks, linear programming relaxations and the parsimonious property in MATHEMATICAL PROGRAMMING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf01585867

    DOI

    http://dx.doi.org/10.1007/bf01585867

    DIMENSIONS

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


    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/0103", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Numerical and Computational Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Mathematics, MIT, 02139, Cambridge, MA, USA", 
              "id": "http://www.grid.ac/institutes/grid.116068.8", 
              "name": [
                "Department of Mathematics, MIT, 02139, Cambridge, MA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Goemans", 
            "givenName": "Michel", 
            "id": "sg:person.07405110736.24", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07405110736.24"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Laboratory for Computer Science, MIT, 02139, Cambridge, MA, USA", 
              "id": "http://www.grid.ac/institutes/grid.116068.8", 
              "name": [
                "Laboratory for Computer Science, MIT, 02139, Cambridge, MA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kleinberg", 
            "givenName": "Jon", 
            "id": "sg:person.011522233557.04", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011522233557.04"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01581256", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023657920", 
              "https://doi.org/10.1007/bf01581256"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01580607", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011806595", 
              "https://doi.org/10.1007/bf01580607"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0120913", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023409631", 
              "https://doi.org/10.1007/bfb0120913"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02097807", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028904969", 
              "https://doi.org/10.1007/bf02097807"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1998-06", 
        "datePublishedReg": "1998-06-01", 
        "description": "Given a tour visitingn points in a metric space, thelatency of one of these pointsp is the distance traveled in the tour before reachingp. Theminimum latency problem (MLP) asks for a tour passing throughn given points for which the total latency of then points is minimum; in effect, we are seeking the tour with minimum average \u201carrival time\u201d. This problem has been studied in the operations research literature, where it has also been termed the \u201cdelivery-man problem\u201d and the \u201ctraveling repairman problem\u201d. The approximability of the MLP was first considered by Sahni and Gonzalez in 1976; however, unlike the classical traveling salesman problem (TSP), it is not easy to give any constant-factor approximation algorithm for the MLP. Recently, Blum et al. (A. Blum, P. Chalasani, D. Coppersimith, W. Pulleyblank, P. Raghavan, M. Sudan, Proceedings of the 26th ACM Symposium on the Theory of Computing, 1994, pp. 163\u2013171) gave the first such algorithm, obtaining an approximation ratio of 144. In this work, we develop an algorithm which improves this ratio to 21.55; moreover, combining our algorithm with a recent result of Garg (N. Garg, Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, 1996, pp. 302\u2013309) provides an approximation ratio of 10.78. The development of our algorithm involves a number of techniques that seem to be of interest from the perspective of the TSP and its variants more generally. \u00a9 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf01585867", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1047630", 
            "issn": [
              "0025-5610", 
              "1436-4646"
            ], 
            "name": "Mathematical Programming", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1-2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "82"
          }
        ], 
        "keywords": [
          "Traveling Salesman Problem", 
          "approximation ratio", 
          "constant-factor approximation algorithm", 
          "operations research literature", 
          "metric spaces", 
          "approximation algorithm", 
          "classical traveling salesman problem", 
          "first such algorithm", 
          "salesman problem", 
          "such algorithms", 
          "Traveling Repairman Problem", 
          "repairman problem", 
          "recent results", 
          "arrival time", 
          "algorithm", 
          "problem", 
          "number of techniques", 
          "approximability", 
          "Delivery Man Problem", 
          "latency problem", 
          "point", 
          "total latency", 
          "Blum", 
          "space", 
          "Sahni", 
          "thelatency", 
          "Garg", 
          "MLP", 
          "distance", 
          "technique", 
          "number", 
          "al", 
          "ratio", 
          "tour", 
          "work", 
          "results", 
          "interest", 
          "Gonzalez", 
          "time", 
          "literature", 
          "variants", 
          "effect", 
          "research literature", 
          "latency", 
          "perspective", 
          "development"
        ], 
        "name": "An improved approximation ratio for the minimum latency problem", 
        "pagination": "111-124", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1039520075"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01585867"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01585867", 
          "https://app.dimensions.ai/details/publication/pub.1039520075"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-10T09:50", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/article/article_303.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf01585867"
      }
    ]
     

    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/bf01585867'

    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/bf01585867'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01585867'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01585867'


     

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

    129 TRIPLES      22 PREDICATES      76 URIs      64 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01585867 schema:about anzsrc-for:01
    2 anzsrc-for:0103
    3 schema:author N77793cad98154cc6a0dcad10c3132f87
    4 schema:citation sg:pub.10.1007/bf01580607
    5 sg:pub.10.1007/bf01581256
    6 sg:pub.10.1007/bf02097807
    7 sg:pub.10.1007/bfb0120913
    8 schema:datePublished 1998-06
    9 schema:datePublishedReg 1998-06-01
    10 schema:description Given a tour visitingn points in a metric space, thelatency of one of these pointsp is the distance traveled in the tour before reachingp. Theminimum latency problem (MLP) asks for a tour passing throughn given points for which the total latency of then points is minimum; in effect, we are seeking the tour with minimum average “arrival time”. This problem has been studied in the operations research literature, where it has also been termed the “delivery-man problem” and the “traveling repairman problem”. The approximability of the MLP was first considered by Sahni and Gonzalez in 1976; however, unlike the classical traveling salesman problem (TSP), it is not easy to give any constant-factor approximation algorithm for the MLP. Recently, Blum et al. (A. Blum, P. Chalasani, D. Coppersimith, W. Pulleyblank, P. Raghavan, M. Sudan, Proceedings of the 26th ACM Symposium on the Theory of Computing, 1994, pp. 163–171) gave the first such algorithm, obtaining an approximation ratio of 144. In this work, we develop an algorithm which improves this ratio to 21.55; moreover, combining our algorithm with a recent result of Garg (N. Garg, Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, 1996, pp. 302–309) provides an approximation ratio of 10.78. The development of our algorithm involves a number of techniques that seem to be of interest from the perspective of the TSP and its variants more generally. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    11 schema:genre article
    12 schema:inLanguage en
    13 schema:isAccessibleForFree false
    14 schema:isPartOf N319411bf937f4663908e18680d85f6aa
    15 N5d3b1372825b484883d299a950fd3e28
    16 sg:journal.1047630
    17 schema:keywords Blum
    18 Delivery Man Problem
    19 Garg
    20 Gonzalez
    21 MLP
    22 Sahni
    23 Traveling Repairman Problem
    24 Traveling Salesman Problem
    25 al
    26 algorithm
    27 approximability
    28 approximation algorithm
    29 approximation ratio
    30 arrival time
    31 classical traveling salesman problem
    32 constant-factor approximation algorithm
    33 development
    34 distance
    35 effect
    36 first such algorithm
    37 interest
    38 latency
    39 latency problem
    40 literature
    41 metric spaces
    42 number
    43 number of techniques
    44 operations research literature
    45 perspective
    46 point
    47 problem
    48 ratio
    49 recent results
    50 repairman problem
    51 research literature
    52 results
    53 salesman problem
    54 space
    55 such algorithms
    56 technique
    57 thelatency
    58 time
    59 total latency
    60 tour
    61 variants
    62 work
    63 schema:name An improved approximation ratio for the minimum latency problem
    64 schema:pagination 111-124
    65 schema:productId N87d51874d5654d328557d387a7313428
    66 N995ce4cee7fc4a348d8616ce03b2d703
    67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039520075
    68 https://doi.org/10.1007/bf01585867
    69 schema:sdDatePublished 2022-05-10T09:50
    70 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    71 schema:sdPublisher Ndca1545a875e4a7193cb3ff2270351b3
    72 schema:url https://doi.org/10.1007/bf01585867
    73 sgo:license sg:explorer/license/
    74 sgo:sdDataset articles
    75 rdf:type schema:ScholarlyArticle
    76 N319411bf937f4663908e18680d85f6aa schema:volumeNumber 82
    77 rdf:type schema:PublicationVolume
    78 N37b1147d21fb4dc38f81f7d81373fa36 rdf:first sg:person.011522233557.04
    79 rdf:rest rdf:nil
    80 N5d3b1372825b484883d299a950fd3e28 schema:issueNumber 1-2
    81 rdf:type schema:PublicationIssue
    82 N77793cad98154cc6a0dcad10c3132f87 rdf:first sg:person.07405110736.24
    83 rdf:rest N37b1147d21fb4dc38f81f7d81373fa36
    84 N87d51874d5654d328557d387a7313428 schema:name dimensions_id
    85 schema:value pub.1039520075
    86 rdf:type schema:PropertyValue
    87 N995ce4cee7fc4a348d8616ce03b2d703 schema:name doi
    88 schema:value 10.1007/bf01585867
    89 rdf:type schema:PropertyValue
    90 Ndca1545a875e4a7193cb3ff2270351b3 schema:name Springer Nature - SN SciGraph project
    91 rdf:type schema:Organization
    92 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    93 schema:name Mathematical Sciences
    94 rdf:type schema:DefinedTerm
    95 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    96 schema:name Numerical and Computational Mathematics
    97 rdf:type schema:DefinedTerm
    98 sg:journal.1047630 schema:issn 0025-5610
    99 1436-4646
    100 schema:name Mathematical Programming
    101 schema:publisher Springer Nature
    102 rdf:type schema:Periodical
    103 sg:person.011522233557.04 schema:affiliation grid-institutes:grid.116068.8
    104 schema:familyName Kleinberg
    105 schema:givenName Jon
    106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011522233557.04
    107 rdf:type schema:Person
    108 sg:person.07405110736.24 schema:affiliation grid-institutes:grid.116068.8
    109 schema:familyName Goemans
    110 schema:givenName Michel
    111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07405110736.24
    112 rdf:type schema:Person
    113 sg:pub.10.1007/bf01580607 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011806595
    114 https://doi.org/10.1007/bf01580607
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/bf01581256 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023657920
    117 https://doi.org/10.1007/bf01581256
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/bf02097807 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028904969
    120 https://doi.org/10.1007/bf02097807
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/bfb0120913 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023409631
    123 https://doi.org/10.1007/bfb0120913
    124 rdf:type schema:CreativeWork
    125 grid-institutes:grid.116068.8 schema:alternateName Department of Mathematics, MIT, 02139, Cambridge, MA, USA
    126 Laboratory for Computer Science, MIT, 02139, Cambridge, MA, USA
    127 schema:name Department of Mathematics, MIT, 02139, Cambridge, MA, USA
    128 Laboratory for Computer Science, MIT, 02139, Cambridge, MA, USA
    129 rdf:type schema:Organization
     




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


    ...