ما هو أقصر Superstring مقابل $ \ {c (ab) ^ k، (ba) ^ k، (ab) ^ k c \} $؟

Question

في هذه الورقة على PDF الصفحة 3، يعطون $ \ {c (ab) ^ k، (ba) ^ k، (ab) ^ kc \} $ كمثال للمدخلات إلى الخوارزمية الجشعة للحصول على أقصر SUBERSTRING التي تسبب لها نسبة تقريبية من 2.

بقدر ما أستطيع أن أقول، أقصر Superstring من تلك المجموعة إما $ c (ab) ^ kc (ba) ^ k $ أو $ B (AB) ^ KC (AB) ^ K $ - في كلتا الحالتين، الطول هو $ 4k + 2 $ وبعد لسوء الحظ، هذا يتناقض مع المطالبة بالورقة التي تنتج الجشع سلسلة من الطول 2 أضعف الأسماء المثلى.

• li> دون فقدان العمومية، يمكننا أن نفترض أن الجشع لن يخرج أبدا سلسلة أطول من تسلسل مجموعة المدخلات الخاصة به - إذا تم وصف الخوارزمية الجشع حقا بهذه الطريقة، فيمكننا فقط إضافة بيان إذا كان للتحقق من هذه الحالة وإرجاع التسلسل بدلا من ذلك.
• طول تسلسل سلاسل الإدخال هو 6 أكيال + 2 $ .
• لجميع $ k \ in \ mathbb {n} $ ، $ 1 \ le \ frac {6K + 2} {4K + 2} \ Le 1.5 $
• لذلك إما أن نسبة التقريب لأي خوارزمية معقولة على هذه الفئة من المشكلات يجب أن تكون أقل من أو تساوي 1.5، أو ما أعتقد أنه أقصر ضعيف ليس في الواقع أقصر واحد.

هل يمكن لشخص إما أن يشرح سبب عدم عمل هذا الخط من الجدال هذا، أو يقول ما هو أقصر Superstring الفعلي لهذه المجموعة؟

Answer 1

superstring أقصر هو $ c (ab) ^ {k + 1} c $ ، والتي لديها طول 2K دولار+4 $ .