Computation of the Closest string Problem Theorem: Closest string problem is NP-hard (K. Lanctot, M. Li, B Ma, S. Wang, and L Zhang 1999) A 4/3(1+) approximation (K. Lanctot, M. Li, B Ma, S. Wang, and L. Zhang 1999) (. Gasieniec, J. Jansson, and A Lingas 1999) A PTAS was presented for the problem (M.Li, B. Ma, and L. Wang, 1999) 2021/1/29 16
2021/1/29 16 Computation of the Closest String Problem Theorem: Closest string problem is NP-hard. (K. Lanctot, M. Li, B. Ma, S. Wang, and L. Zhang 1999) A 4/3(1+) approximation: (K. Lanctot, M. Li, B. Ma, S. Wang, and L. Zhang 1999) (L. Gasieniec, J. Jansson, and A. Lingas 1999) A PTAS was presented for the problem (M. Li, B. Ma, and L. Wang, 1999)
Linear Programming Approach The optimization problem min d d(Ssx)≤d,i=1,2,…,n 2021/1/29 17
2021/1/29 17 Linear Programming Approach The optimization problem: min d; d(si , x) d, i =1, 2, … , n
Linear Programming Approach The optimization problem min d 4∈%,a L 1 <L aex(S小,a)xa≤d,i=1,2,…,n 0, a 0-1 variable denoting whether xl-a .sll a)-denote whether sill=a jaa fractional solution to the above LP 2021/1/29 18
2021/1/29 18 The optimization problem min d; a xj,a = 1, j =1, 2 , … , L ; 1 j L a (si [j], a) xj,a d, i = 1, 2, … , n. • xj,a – 0 -1 variable denoting whether x[j] = a • (si [j], a) – denote whether si [j] = a • x'j,a – a fractional solution to the above LP Linear Programming Approach
Linear Programming Approach(continued) Randomized rounding with probability wj a set:=1 Theorem: For any c>0, if L 2 4(n n)&, and d =aL then d(s12x)≤d(1+8) Co When L< 4(In n)/g: enumerate all possible strings oflength L 2021/1/29 19
2021/1/29 19 Linear Programming Approach (continued) Randomized Rounding: with probability x' j,a , set xj,a = 1. Theorem: For any > 0, if L 4(ln n)/ 2 , and d =(L), then d(si , x ) d(1+). When L< 4(ln n)/ 2 :enumerate all possible strings of length L
when d is small (a<OD) Theorem: Let lsip,2y…,i≤ n and g ili2.ir be the set of positions where Sil, Si2, ., Sir agree. There exist indices 1≤i1,i2,…,ir≤ n such that for any St ∈Qnnm|S≠S小ands≠s(2r-1)d when max d(s, S)>1+1/(2r-1) Note that Si and s can be different in many bits in Oili2. ir However. the effect on each s, e B is not bad 2021/1/29 20
2021/1/29 20 when d is small (d < O(L)) Theorem: Let 1 i1 , i2 , …, ir n and Qi1,i2,…,ir be the set of positions where si1 , si2 , …, sir agree. There exist indices 1 i1 , i2 , …, ir n such that for any sl |{j Qi1,i2,…,ir | si1 [j] sl [j] and si1 [j] s[j]}| 1/(2r-1) d, when max d(si , sj ) > 1+1/(2r-1). Note that si1 and s can be different in many bits in Qi1,i2,…,ir . However, the effect on each sl B is not bad