Name
Abstract | ||
|---|---|---|
The Shortest Common Supersequence Problem (SCSP) is a well-known hard combinatorial optimization problem that formalizes many real world problems. This paper presents a novel randomized search strategy, called probabilistic beam search (PBS), based on the hybridization between beam search and greedy constructive heuristics. PBS is competitive (and sometimes better than) previous state-of-the-art algorithms for solving the SCSP. The paper describes PBS and provides an experimental analysis (including comparisons with previous approaches) that demonstrate its usefulness. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-71615-0_4 | EvoCOP |
Keywords | Field | DocType |
shortest common supersequence problem,probabilistic beam search,greedy constructive heuristics,novel randomized search strategy,beam search,experimental analysis,probabilistic beam search approach,previous state-of-the-art algorithm,real world problem,well-known hard combinatorial optimization,previous approach,random search,shortest common supersequence | Memetic algorithm,String searching algorithm,Shortest common supersequence,Mathematical optimization,Combinatorial optimization problem,Beam search,Greedy algorithm,Theoretical computer science,Vertex cover,Probabilistic logic,Mathematics | Conference |
Volume | ISSN | Citations |
4446 | 0302-9743 | 7 |
PageRank | References | Authors |
0.59 | 13 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christian Blum | 1 | 981 | 72.64 |
| Carlos Cotta | 2 | 441 | 36.10 |
| Antonio Fernández | 3 | 801 | 49.47 |
| José E. Gallardo | 4 | 57 | 6.99 |