MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEInsertion and Sorting in a Sequence of Numbers Minimizing the Maximum Sum of a Contiguous Subsequence
par Ricardo Corea, Professeur UFC Fortaleza Bresil
| Date : | 06/09/12 | | Time : | 10:30 | | Location : | Euler Violet |
Ă‚' Let $A$ be a sequence of $n geq 0$ real numbers. A subsequence of $A$
is a sequence of contiguous elements of $A$. A emph{maximum scoring subsequence} of $A$ is a
subsequence with largest sum of its elements. The emph{Maximum Scoring
Subsequence (MSS)} problem is that of finding a maximum scoring subsequence of a given
sequence $A$. The MSS problem can be solved in $O(n)$ time
by Kadane's dynamic programming algorithm. The MSS problem
has several applications in practice, notably in Computational Biology, where
maximum scoring subsequences correspond to various structures of interest.
We consider in this paper two problems related to the MSS one. Both of them
arise in the context of buffer memory minimization in computer networks and, to
the best of our knowledge, have not been defined in the literature.
The first one, which is called emph{Insertion in a Sequence with Scores (ISS)},
consists in inserting a given real number $x$ in $A$ in such a way to minimize
the sum of a maximum scoring subsequence of the resulting sequence, which can
be easily done in $O(n^2)$ time by successively
applying Kadane's algorithm to compute the maximum scoring
subsequence of the resulting sequence corresponding to each possible insertion
position for $x$. We show in this paper that the ISS problem can be solved in
linear time and space with a more specialized algorithm. The second problem we
consider in this paper is the emph{Sorting a Sequence by Scores (SSS)} one, stated as follows: find a permutation $A'$ of $A$ that minimizes the sum of a maximum scoring subsequence.
We show that the SSS problem is in NP-Hard and give a 2-approximation algorithm for it.
Page des séminaires
| 
