[CPM-SPIRE-L] Master Internship offer in Text Algorithms and optimisation

[Rivals Eric]

Internship Offer.

Main Webpage:  http://www2.lirmm.fr/~rivals/INTERN/

Keywords: text algorithms, approximation, superstring, stringology

Tutor: Eric Rivals (rivals at lirmm.fr)
Tel. : 04 67 41 86 64

Location: LIRMM (http://www.lirmm.fr), Montpellier, France

Duration: 4 to 6 months

** Description

The Shortest Superstring Problem (SSP) is a well known problem. For a 
set $P$ of finite strings, it seeks the smallest superstring (a string 
$w$ where each string of $P$ is a substring of $w$). This problem is 
NP-hard (Gallant et al. 1980) and there exist many algorithms of 
approximation (Blum et al. 1994, Paluch 2014). The reoptimization of the 
Shortest Superstring Problem describes the following scenario: given a 
set of strings together with an optimal solution for it, we want to find 
a good solution for a locally modified instance (addition, deletion or 
modification of a string or a set of strings).

This research topics of this internship aims at survey the literature 
and propose ideas for one of the following goals:
1. Find an algorithm for reoptimization of the Shortest Superstring 
Problem for different locally modified instances, for example :
    - addition of a string (Bilo et al. 2011)
    - modification of a string (insertion, deletion or mutation)
2. Given a set $P$ of strings, an algorithm $\mathcal{A}$ with a ratio 
of approximation $\alpha$ and a solution $w$ of $\mathcal{A}$ for $P$, 
we want to find the ratio between $w$ and the solution of $\mathcal{A}$ 
for different locally modified instances of $P$.

This topic is well suited to a candidate with a good background in 
algorithmics and complexity.

Best regards,
Eric Rivals

-- 
Eric RIVALS (PhD) - rivals at lirmm.fr - www.lirmm.fr/~rivals
CNRS Research Director & Head of GDR Bioinformatique Moléculaire
LIRMM - UMR 5506 & Univ Montpellier 2 (CC 05016)
860 rue de St Priest - 34095 Montpellier cedex 5 FRANCE
Tel. (33 or 0 from France) 4 67 41 86 64
Fax. (33 or 0 from France) 4 67 41 85 00
http://www.gdr-bim.cnrs.fr


-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2935 bytes
Desc: Signature cryptographique S/MIME
Url : https://fenris.cs.ucr.edu/pipermail/cpm-spire-l/attachments/20150119/e6d010e9/attachment.bin