$ \ {C (AB) ^ K, (BA) ^ K, (AB) ^ K C \} $에 대한 가장 짧은 초과력은 무엇입니까?

Question

in 이 백서 page 3, 그들은 $ \ {C (AB) ^ K, (BA) ^ K, (AB) ^ KC \} $ 탐욕스러운 알고리즘에 대한 입력의 예로서 그것이 2의 근사 비율을 갖게하는 초선생.

내가 말할 수있는 한, 그 세트의 가장 짧은 슈퍼 스트링은 $ c (ab) ^ kc (ba) ^ k $ 또는 $ b (ab) ^ kc (ab) ^ k $ - 어느 쪽이든, 길이는 $ 4k + 2 $ ...에 불행히도, 이것은 탐욕이 최적의 초선회의 길이 2 배의 길이의 문자열을 출력하는 용지에서 주장을 모순합니다.

• 일반성이 손실되지 않고, 우리는 탐욕이 입력 세트의 연결보다 긴 스트링을 결코 출력하지 않을 것이라고 가정 할 수 있습니다. 탐욕스러운 알고리즘이 실제로 설명 된 경우, IF 문을 그 대소 문자를 확인하도록 추가 할 수 있습니다. 대신 연결을 반환하십시오.
• 입력 문자열의 연결의 길이는 $ 6k + 2 $
입니다.
• 모든 $ k \ \ mathbb {n} $ , $ 1 \ le \ frac {6k + 2} {4K + 2} \ LE 1.5 $
• 이 문제 의이 종류의 합리적인 알고리즘에 대한 근사 비율은 1.5 이하이거나 가장 짧은 초선생이 실제로 가장 짧은 것도 아닙니다.

누군가 가이 논증 라인이 작동하지 않는 이유를 설명 하거나이 세트의 실제 최단선 슈퍼 스트링이 무엇인지 설명 할 수 있습니까?

Answer 1

짧은 초선생은 $ c (ab) ^ {k + 1} c $ , 길이 $ 2k+4 $ .