Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/12546Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Arora, S. | en |
| dc.contributor.author | Karakostas, G. | en |
| dc.date.accessioned | 2015-11-24T17:21:57Z | - |
| dc.date.available | 2015-11-24T17:21:57Z | - |
| dc.identifier.issn | 0097-5397 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/12546 | - |
| dc.rights | Default Licence | - |
| dc.subject | minimum latency tour | en |
| dc.subject | traveling repairman | en |
| dc.subject | search ratio | en |
| dc.subject | randomized search ratio | en |
| dc.subject | vehicle routing | en |
| dc.subject | quasi-polynomial approximation schemes | en |
| dc.subject | approximation algorithms | en |
| dc.subject | traveling salesman problem | en |
| dc.title | Approximation schemes for minimum latency problems | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.identifier.primary | Doi 10.1137/S0097539701399654 | - |
| heal.identifier.secondary | <Go to ISI>://000185629400011 | - |
| heal.identifier.secondary | http://epubs.siam.org/doi/abs/10.1137/S0097539701399654 | - |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.publicationDate | 2003 | - |
| heal.abstract | The minimum latency problem, also known as the traveling repairman problem, is a variant of the traveling salesman problem in which the starting node of the tour is given and the goal is to minimize the sum of the arrival times at the other nodes. We present a quasi-polynomial time approximation scheme (QPTAS) for this problem when the instance is a weightedtree, when the nodes lie in R(d) for some fixed d, and for planar graphs. We also present a polynomial time constant factor approximation algorithm for the general metric case. The currently best polynomial time approximation algorithm for general metrics, due to Goemans and Kleinberg, computes a 3.59-approximation. | en |
| heal.journalName | Siam Journal on Computing | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά). ΜΑΘ | |
Files in This Item:
There are no files associated with this item.
This item is licensed under a Creative Commons License
