Sträng jämförelse är ett grundläggande problem inom datavetenskap, med tillämpningar inom områden som beräkningsbiologi, textbehandling och kompression. I det här dokumentet tar vi upp minsta gemensamma strängpartition problem, en sträng jämförelse problem med snäv koppling till problemet med sortering genom reverseringar med dubbletter, ett nyckelproblem i genom omorganisation. En partition av en sträng A är en sekvens P = (P 1, P 2,. .., P m ) av strängar, kallas blocken, vars konkatetering är lika med A. Eftersom en partition P av en sträng A och en partition Q av en sträng B, säger vi att paret P, Q är en gemensam partition av A och B om Q är en permutation av P. Det minsta gemensamma strängpartition problemet (MCSP) är att hitta en gemensam partition av två strängar A och B med det minsta antalet block. Den begränsade versionen av MCSP där varje bokstav inträffar som mest k gånger i varje inmatningssträng, betecknas av k-MCSP. I detta dokument visar vi att 2-MCSP (och därmed MCSP) är NP-hård och dessutom även APX-hård. Vi beskriver en 1.1037-approximation för 2-MCSP och en linjär 4-approximeringsalgoritm för 3-MCSP. Vi känner inte till några bättre approximationer. * Preliminär version av detta arbete presenterades på den 15: e internationella symposium om algoritmer och beräkning [9].
är NP-hård, och även APX-hård REF.
Minimum Common String Partition Problem: Hardness and Approximations
{'venue': 'ISAAC', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}