<div class="csl-bib-body">
<div class="csl-entry">Mayerhofer, J., Kirchweger, M., Huber, M., & Raidl, G. (2022). A Beam Search for the Shortest Common Supersequence Problem Guided by an Approximate Expected Length Calculation. In <i>Evolutionary Computation in Combinatorial Optimization</i> (pp. 127–142). Springer Nature Switzerland AG. https://doi.org/10.34726/3442</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/142513
-
dc.identifier.uri
https://doi.org/10.34726/3442
-
dc.description.abstract
The shortest common supersequence problem (SCSP) is a well-known NP-hard problem with many applications, in particular in data compression, computational molecular biology, and text editing. It aims at finding for a given set of input strings a shortest string such that every string from the set is a subsequence of the computed string. Due to its NP-hardness, many approaches have been proposed to tackle the SCSP heuristically. The currently best-performing one is based on beam search (BS). In this paper, we present a novel heuristic (AEL) for guiding a BS, which approximates the expected length of an SCSP of random strings, and embed the proposed heuristic into a multilevel probabilistic beam search (MPBS). To overcome the arising scalability issue of the guidance heuristic, a cut-off approach is presented that reduces large instances to smaller ones. The proposed approaches are tested on two established sets of benchmark instances. MPBS guided by AEL outperforms the so far leading method on average on a set of real instances. For many instances new best solutions could be obtained.
en
dc.description.sponsorship
Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.language.iso
en
-
dc.relation.ispartofseries
Lecture Notes in Computer Science
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Beam Search
en
dc.subject
Shortest Common Supersequence Problem
en
dc.title
A Beam Search for the Shortest Common Supersequence Problem Guided by an Approximate Expected Length Calculation
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.rights.license
Urheberrechtsschutz
de
dc.rights.license
In Copyright
en
dc.identifier.doi
10.34726/3442
-
dc.relation.isbn
978-3-031-04148-8
-
dc.relation.doi
10.1007/978-3-031-04148-8
-
dc.relation.issn
0302-9743
-
dc.description.startpage
127
-
dc.description.endpage
142
-
dc.relation.grantno
W1260-N35
-
dc.rights.holder
The Author(s), under exclusive license to Springer Nature Switzerland
-
dc.type.category
Full-Paper Contribution
-
dc.relation.eissn
1611-3349
-
tuw.booktitle
Evolutionary Computation in Combinatorial Optimization
-
tuw.container.volume
13222
-
tuw.peerreviewed
true
-
tuw.book.ispartofseries
Lecture Notes in Computer Science
-
tuw.relation.publisher
Springer Nature Switzerland AG
-
tuw.relation.publisherplace
Cham, Switzerland
-
tuw.project.title
Doktoratskolleg "Vienna Graduate School on Computational Optimization"
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publisher.doi
10.1007/978-3-031-04148-8_9
-
dc.identifier.libraryid
AC17203498
-
dc.description.numberOfPages
16
-
tuw.author.orcid
0009-0003-2862-6232
-
tuw.author.orcid
0000-0002-3293-177X
-
dc.rights.identifier
Urheberrechtsschutz
de
dc.rights.identifier
In Copyright
en
tuw.event.name
EvoCop2022
en
tuw.event.startdate
20-04-2022
-
tuw.event.enddate
22-04-2022
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Madrid
-
tuw.event.country
ES
-
tuw.event.presenter
Mayerhofer, Jonas
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.openaccessfulltext
Open Access
-
item.cerifentitytype
Publications
-
item.languageiso639-1
en
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.grantfulltext
open
-
item.fulltext
with Fulltext
-
item.mimetype
application/pdf
-
item.openairetype
conference paper
-
crisitem.author.dept
TU Wien
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity