### Skapa referens, olika format (klipp och klistra)

**Harvard**

Damaschke, P. och Bergkvist, A. (2005) *Fast algorithms for finding disjoint subsequences with extremal densities*.

** BibTeX **

@conference{

Damaschke2005,

author={Damaschke, Peter and Bergkvist, Anders},

title={Fast algorithms for finding disjoint subsequences with extremal densities},

booktitle={16th International Symposium on Algorithms and Computation ISAAC 2005, Lecture Notes in Computer Science },

isbn={3-540-30935-7},

pages={714-723},

abstract={We derive fast algorithms for the problem of finding, on
the real line, a prescribed number of intervals of maximum total length that contain at most some prescribed number of points from a given point set. Basically this is a typical
dynamic programming problem, however, for input sizes much bigger than the two parameters we can improve the obvious time bound by selecting a restricted set of candidate intervals that are sufficient to build some optimal solution. As a byproduct, the same idea improves an algorithm for a similar subsequence problem recently
brought up by Chen, Lu and Tang at IWBRA 2005. The problems are motivated by the search for significant patterns in certain biological data. While the algorithmic idea for the asymptotic worst-case bound is rather evident, we also consider further heuristics to save even more time in typical instances. One of them, described in this paper, leads to an apparently open problem of computational geometry flavour (where we are seeking a subquadratic algorithm) which might be interesting in itself.},

year={2005},

keywords={data mining, holes in data, sparse dynamic programming},

}

** RefWorks **

RT Conference Proceedings

SR Print

ID 9566

A1 Damaschke, Peter

A1 Bergkvist, Anders

T1 Fast algorithms for finding disjoint subsequences with extremal densities

YR 2005

T2 16th International Symposium on Algorithms and Computation ISAAC 2005, Lecture Notes in Computer Science

SN 3-540-30935-7

SP 714

OP 723

AB We derive fast algorithms for the problem of finding, on
the real line, a prescribed number of intervals of maximum total length that contain at most some prescribed number of points from a given point set. Basically this is a typical
dynamic programming problem, however, for input sizes much bigger than the two parameters we can improve the obvious time bound by selecting a restricted set of candidate intervals that are sufficient to build some optimal solution. As a byproduct, the same idea improves an algorithm for a similar subsequence problem recently
brought up by Chen, Lu and Tang at IWBRA 2005. The problems are motivated by the search for significant patterns in certain biological data. While the algorithmic idea for the asymptotic worst-case bound is rather evident, we also consider further heuristics to save even more time in typical instances. One of them, described in this paper, leads to an apparently open problem of computational geometry flavour (where we are seeking a subquadratic algorithm) which might be interesting in itself.

LA eng

OL 30