On the hardness of approximating spanners

Guy Kortsarz

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء


A k-spanner of a connected graph G = (V, E) is a subgraph Gʹ consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two vertices in Gʹ is larger than that distance in G by no more than a factor of k. This paper concerns the hardness of finding spanners with the number of edges close to the optimum. It is proved that for every fixed k approximating the spanner problem is at least as hard as approximating the set cover problem We also consider a weighted version of the spanner problem. We prove that in the case k = 2 the problem admits an O(log n)-ratio approximation, and in the case k ≥ 5, there is no 2log1-ϵ n-ratio approximation, for any ϵ > 0, unless NP ⊆ DTIME(npolylog n).

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفApproximation Algorithms for Combinatorial Optimization - International Workshop, APPROX 1998, Proceedings
المحررونJosé Rolim, Klaus Jansen
ناشرSpringer Verlag
عدد الصفحات12
رقم المعيار الدولي للكتب (المطبوع)3540647368, 9783540647362
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1998
الحدثInternational Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 1998 - Aalborg, الدنمارك
المدة: ١٨ يوليو ١٩٩٨١٩ يوليو ١٩٩٨

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت1444
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349


!!ConferenceInternational Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 1998

ملاحظة ببليوغرافية

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1998.


أدرس بدقة موضوعات البحث “On the hardness of approximating spanners'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا