A 2+epsilon approximation algorithm for the k-MST problem
Φόρτωση...
Ημερομηνία
Συγγραφείς
Arora, S.
Karakostas, G.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Mathematical Programming
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
For any epsilon > 0 we give a (2 + epsilon)-approximation algorithm for the problem of finding a minimum tree spanning any k vertices in a graph (k-MST), improving a 3-approximation algorithm by Garg [10]. As in [10] the algorithm extends to a (2 + epsilon)-approximation algorithm for the minimum tour that visits any k vertices, provided the edge costs satisfy the triangle inequality.
Περιγραφή
Λέξεις-κλειδιά
k-minimum spanning tree, approximation algorithm, primal-dual schema, trees
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
<Go to ISI>://000236418400008
http://download.springer.com/static/pdf/845/art%253A10.1007%252Fs10107-005-0693-1.pdf?auth66=1390991909_7814733229273a02cc2fd8c0bbcafb6d&ext=.pdf
http://download.springer.com/static/pdf/845/art%253A10.1007%252Fs10107-005-0693-1.pdf?auth66=1390991909_7814733229273a02cc2fd8c0bbcafb6d&ext=.pdf
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών