Closest Substring Problem Instance: Given a set b of n strings of length at least L and an integer d Objective: Find a string s of length l such that for each string S,E B, there is a substring t; of s,(with length D) such that a(,s)≤d Theorem: Closest substring problem is NP-hard (K. Lanctot, M. Li, B Ma, S. Wang, and L. Zhang 1999) A PTAS was given in M. Li, B Ma, and L. Wang 2000 2021/1/292021/1/29 9 Closest Substring Problem Instance: Given a set B of n strings of length at least L, and an integer d Objective: Find a string s of length L such that for each string si  B, there is a substring t i of si (with length L) such that d(s, si )  d Theorem: Closest substring problem is NP-hard. (K. Lanctot, M. Li, B. Ma, S. Wang, and L. Zhang 1999) A PTAS was given in M. Li, B. Ma, and L. Wang 2000