Farthest String Problem(the other half) Instance: Given a set G of n strings of length L, and an integer Objective: Find a string s of length l such that for each string S;∈G,(s,S)≥d Theorem: Farthest String Problem is NP-hard (K. Lanctot, M.Li, B Ma, S. Wang, and L. Zhang, 1999) A PTAS A linear programming random rounding d is very large, i.e, O) (K. Lanctot, M. Li, B Ma, S. Wang, and L. Zhang 1999) 2021/1/29 112021/1/29 11 Farthest String Problem (the other half) Instance: Given a set G of n strings of length L, and an integer d Objective: Find a string s of length L such that for each string si  G, d(s, si )  d. Theorem: Farthest String Problem is NP-hard. (K. Lanctot, M. Li, B. Ma, S. Wang, and L. Zhang, 1999) A PTAS -- A linear programming + random rounding d is very large, i.e, O(L). (K. Lanctot, M. Li, B. Ma, S. Wang, and L. Zhang 1999)