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 11
2021/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)
Computer Science Background Knowledge NP-complete Problems: unlikely to have a polynomial time algorithm to optimally solve the problem A-an approximation algorithm for a minimization problem performance ratio: a number r such that for any instance I A1)OPT)≤r A()- the cost of the solution for instance I produced by A OPTO-the cost of an optimal solution for instance I approximation scheme: an algorithm A with input I and an error bound a that has the performance ratio 1+8 a family of algorithms A, one for each a. 2021/1/29 12
2021/1/29 12 Computer Science Background Knowledge NP-complete Problems: unlikely to have a polynomial time algorithm to optimally solve the problem A- an approximation algorithm for a minimization problem. performance ratio: a number r such that for any instance I A(I)/OPT(I) r A(I) - the cost of the solution for instance I produced by A OPT(I) - the cost of an optimal solution for instance I. approximation scheme: an algorithm A with input I and an error bound that has the performance ratio 1+ . a family of algorithms A, one for each
Computer Science Background Knowledge Polynomial time approximation scheme(Ptas): an approximation scheme a that runs in time polynomial in the size of the instance 1, for any fixed a. MAX SNP-hard: unlikely to have a ptas 2021/1/29 13
2021/1/29 13 Computer Science Background Knowledge Polynomial time approximation scheme (PTAS): an approximation scheme A that runs in time polynomial in the size of the instance I, for any fixed . MAX SNP-hard: unlikely to have a PTAS
Summary of our theoretical results Closest string problem: A PTAS (M Li, B Ma, and L Wang, STOC99) Closest substring Problem: A PTAS (Li, Ma, Wang, 2002, JACM) Consensus pattern problem: NP-hard and A PTAS(Li, Ma and Wang, JCSS, 2002) Distinguishing string selection Problem: PTAS Distinguishing Substring Selection Problem: A PTAS (Deng, Li, Li, MA and Wang, SIAM J on Computing, 2003) 2021/1/29 14
2021/1/29 14 Summary of our theoretical results: •Closest string problem: A PTAS (M. Li, B. Ma, and L. Wang, STOC99) •Closest substring Problem: A PTAS (Li, Ma, Wang, 2002, JACM) Consensus pattern problem: NP-hard and A PTAS ( Li, . Ma, and Wang, JCSS, 2002) •Distinguishing string Selection Problem: PTAS •Distinguishing Substring Selection Problem: A PTAS (Deng, Li, Li, MA and Wang, SIAM J. on Computing, 2003)
Our results An approximation scheme that takes an 8>0 as a parameter and finds a string s such that for each string b E B there exists a substring t of b with length L such that d(S,t)≤(1 teab and for any string g∈G d(s,g)2(1-6)d 2021/1/29 15
2021/1/29 15 Our Results An approximation scheme that takes an >0 as a parameter and finds a string s such that for each string b B there exists a substring t of b with length L such that d(s, t) (1+) db , and for any string g G, d(s, g) (1- ) dg