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", 
          "first such algorithm", 
          "approximation algorithm", 
          "metric spaces", 
          "such algorithms", 
          "salesman problem", 
          "Traveling Repairman Problem", 
          "classical traveling salesman problem", 
          "recent results", 
          "algorithm", 
          "problem", 
          "repairman problem", 
          "total latency", 
          "latency problem", 
          "approximability", 
          "number of techniques", 
          "arrival time", 
          "MLP", 
          "point", 
          "space", 
          "Blum", 
          "Sahni", 
          "Garg", 
          "tour", 
          "technique", 
          "number", 
          "Gonzalez", 
          "interest", 
          "work", 
          "results", 
          "literature", 
          "distance", 
          "variants", 
          "al", 
          "research literature", 
          "time", 
          "ratio", 
          "latency", 
          "perspective", 
          "development", 
          "effect", 
          "tour visitingn points", 
          "visitingn points", 
          "thelatency", 
          "pointsp", 
          "reachingp", 
          "Theminimum latency problem", 
          "delivery-man problem"
        ], 
        "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-01-01T18:09", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_300.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.

    134 TRIPLES      22 PREDICATES      81 URIs      69 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 N42ee302cd4ad40fca692d02ac1fef7a8
    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 N82ab386fdbf642ec9a4f9b555d74111e
    15 Nf5b628c70656433a9858567495fde738
    16 sg:journal.1047630
    17 schema:keywords Blum
    18 Garg
    19 Gonzalez
    20 MLP
    21 Sahni
    22 Theminimum latency problem
    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 delivery-man problem
    34 development
    35 distance
    36 effect
    37 first such algorithm
    38 interest
    39 latency
    40 latency problem
    41 literature
    42 metric spaces
    43 number
    44 number of techniques
    45 operations research literature
    46 perspective
    47 point
    48 pointsp
    49 problem
    50 ratio
    51 reachingp
    52 recent results
    53 repairman problem
    54 research literature
    55 results
    56 salesman problem
    57 space
    58 such algorithms
    59 technique
    60 thelatency
    61 time
    62 total latency
    63 tour
    64 tour visitingn points
    65 variants
    66 visitingn points
    67 work
    68 schema:name An improved approximation ratio for the minimum latency problem
    69 schema:pagination 111-124
    70 schema:productId N14c7e09e50cc498094486687229781df
    71 N19075447e5eb4f8fb0811e1ef84331f2
    72 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039520075
    73 https://doi.org/10.1007/bf01585867
    74 schema:sdDatePublished 2022-01-01T18:09
    75 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    76 schema:sdPublisher Ne7ebdd7892fd4162985b172f63d57285
    77 schema:url https://doi.org/10.1007/bf01585867
    78 sgo:license sg:explorer/license/
    79 sgo:sdDataset articles
    80 rdf:type schema:ScholarlyArticle
    81 N14c7e09e50cc498094486687229781df schema:name doi
    82 schema:value 10.1007/bf01585867
    83 rdf:type schema:PropertyValue
    84 N19075447e5eb4f8fb0811e1ef84331f2 schema:name dimensions_id
    85 schema:value pub.1039520075
    86 rdf:type schema:PropertyValue
    87 N42ee302cd4ad40fca692d02ac1fef7a8 rdf:first sg:person.07405110736.24
    88 rdf:rest N59e241b66d73410d9739aef01946417d
    89 N59e241b66d73410d9739aef01946417d rdf:first sg:person.011522233557.04
    90 rdf:rest rdf:nil
    91 N82ab386fdbf642ec9a4f9b555d74111e schema:volumeNumber 82
    92 rdf:type schema:PublicationVolume
    93 Ne7ebdd7892fd4162985b172f63d57285 schema:name Springer Nature - SN SciGraph project
    94 rdf:type schema:Organization
    95 Nf5b628c70656433a9858567495fde738 schema:issueNumber 1-2
    96 rdf:type schema:PublicationIssue
    97 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    98 schema:name Mathematical Sciences
    99 rdf:type schema:DefinedTerm
    100 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    101 schema:name Numerical and Computational Mathematics
    102 rdf:type schema:DefinedTerm
    103 sg:journal.1047630 schema:issn 0025-5610
    104 1436-4646
    105 schema:name Mathematical Programming
    106 schema:publisher Springer Nature
    107 rdf:type schema:Periodical
    108 sg:person.011522233557.04 schema:affiliation grid-institutes:grid.116068.8
    109 schema:familyName Kleinberg
    110 schema:givenName Jon
    111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011522233557.04
    112 rdf:type schema:Person
    113 sg:person.07405110736.24 schema:affiliation grid-institutes:grid.116068.8
    114 schema:familyName Goemans
    115 schema:givenName Michel
    116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07405110736.24
    117 rdf:type schema:Person
    118 sg:pub.10.1007/bf01580607 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011806595
    119 https://doi.org/10.1007/bf01580607
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/bf01581256 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023657920
    122 https://doi.org/10.1007/bf01581256
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/bf02097807 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028904969
    125 https://doi.org/10.1007/bf02097807
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/bfb0120913 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023409631
    128 https://doi.org/10.1007/bfb0120913
    129 rdf:type schema:CreativeWork
    130 grid-institutes:grid.116068.8 schema:alternateName Department of Mathematics, MIT, 02139, Cambridge, MA, USA
    131 Laboratory for Computer Science, MIT, 02139, Cambridge, MA, USA
    132 schema:name Department of Mathematics, MIT, 02139, Cambridge, MA, USA
    133 Laboratory for Computer Science, MIT, 02139, Cambridge, MA, USA
    134 rdf:type schema:Organization
     




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


    ...