Approximation schemes for minimum latency problems
Φόρτωση...
Ημερομηνία
Συγγραφείς
Arora, S.
Karakostas, G.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Siam Journal on Computing
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
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.
Περιγραφή
Λέξεις-κλειδιά
minimum latency tour, traveling repairman, search ratio, randomized search ratio, vehicle routing, quasi-polynomial approximation schemes, approximation algorithms, traveling salesman problem
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
<Go to ISI>://000185629400011
http://epubs.siam.org/doi/abs/10.1137/S0097539701399654
http://epubs.siam.org/doi/abs/10.1137/S0097539701399654
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών