Key points are not available for this paper at this time.
نسترجع المهمة الكلاسيكية المتمثلة في إيجاد أقصر جولة لـ n نقطة في الفضاء الإقليدي ذا الأبعاد d، لأي ثابت محدد d ≥ 2. نحن نحدد الاعتماد الأمثل على الزمن في تنفيذ خوارزمية تحسب جولة تقريبية (1 + ε)، تحت فرضية معقولة. على وجه التحديد، نقدم خوارزمية تعمل في 2^{O(1/ε^{d-1})} n^n زمن. هذا يحسن من أدنى اعتماد سابق على الزمن في تنفيذ الخوارزمية (1/ε)^{O(1/ε^{d-1})} n^n من خوارزمية راو وسميث (STOC 1998). كما نوضح أن خوارزمية 2^{o(1/ε^{d-1})}poly(n) ستخالف فرضية زمن الفجوة الأسية (Gap-ETH). تبني خوارزميتنا الجديدة على الطرق القائمة على الشجرة الرباعية التي اقترحها آروتا (J. ACM 1998) في البداية، لكنها تضيف فكرة جديدة نسميها التصحيح الحساس للازدحام. على مستوى عالٍ، فهذا يسمح بمدى دقة تبسيط الجولة بالاعتماد على مدى ازدحامها محلياً. نوضح أن تقنيتنا تمتد إلى مشكلات أخرى، من خلال إظهار أن خوارزمية شجرة ستاينر وشجرة ستاينر المستقيمة تحقق نفس زمن التنفيذ. نكمل نتائجنا بحد أدنى مطابق لـ Gap-ETH لشجرة ستاينر المستقيمة.
درس كيسفالودي-باك وآخرون (Mon,) هذا السؤال.