Show simple item record

AuthorLorenz, Jan-Hendrikdc.contributor.author
Date of accession2022-01-26T14:57:35Zdc.date.accessioned
Available in OPARU since2022-01-26T14:57:35Zdc.date.available
Year of creation2021dc.date.created
Date of first publication2021-09-16dc.date.issued
AbstractRestarting is a technique employed by many randomized algorithms for a variety of different problems. If the algorithm has not been successful after a certain time, the algorithm is reset, and a new try is started that is independent of the past attempt. For some problems, restarts can be used to achieve improved expected runtimes, while for others, restarts deteriorate the expected runtimes. For this reason, it is essential to gain insight into when restarts are beneficial and which restart strategy should be chosen. In this thesis, we first show that the problem of deciding whether restarts have a positive effect is NP-hard, even when the underlying probability distribution is fully known. Furthermore, we prove that the computation of the expected runtime for a given restart strategy is #P-hard. On the other hand, an efficient (4+epsilon) approximation algorithm for the optimal restart strategy is provided. In this context, we frequently assume that a given function is, in fact, a valid description of a probability distribution. The complexity of verifying these assumptions is also analyzed. We show that deciding whether a given function corresponds to a cumulative probability function is CoNP-hard. Moreover, deciding whether a given function represents a probability mass function is P(#P)-hard. Although these problems are challenging in general, we show certain special cases in which they are simple. In particular, we introduce conditions for the usefulness of restarts as well as for determining an optimal restart strategy. It is shown that some typical parameters have either no or only a limited influence on the restart properties. Furthermore, it is proven that restarts are always useful for so-called long-tail distributions. By means of these results, it is possible to considerably simplify the analysis of many probability distributions; consequently, the NP-hardness does not pose an obstacle in many practical applications. Luby's strategy is a popular restart strategy in practical applications. Suppose the underlying probability distribution is defined on the natural numbers. In that case, Luby's strategy provides a certain performance guarantee: The expected runtime using Luby's strategy is at most worse by a logarithmic factor than the expected runtime using the optimal restart strategy. However, we prove that this is not a general property, and furthermore, there is no universal restart strategy providing such a performance guarantee. On the other hand, we identify conditions under which such universal strategies do exist. A particular obstacle for determining an optimal restart strategy is that the underlying probability distribution has to be known. However, that is usually not the case for unsolved instances. To circumvent this problem, we design a machine learning pipeline predicting the runtime distribution of unseen instances. An optimal restart strategy is derived for the SAT solver probSAT based on these predicted distributions. We experimentally demonstrate that this approach statistically significantly improves the performance of probSAT. We achieve an average speedup factor of more than 50 on the domain on which probSAT encounters the most significant difficulties. Lastly, restarts are also considered in an environment in which a deadline is present and in which the corresponding algorithm runs in parallel. We specify a condition for finding the optimal restart strategy and show that increasing the number of utilized processors has a super-linear benefit in this scenario.dc.description.abstract
Languageen_USdc.language.iso
PublisherUniversität Ulmdc.publisher
LicenseLizenz Adc.rights
Link to license texthttps://oparu.uni-ulm.de/xmlui/licenseA_v1dc.rights.uri
KeywordRestart strategydc.subject
KeywordRuntime distributiondc.subject
KeywordLong-tailed distributiondc.subject
KeywordSAT solvingdc.subject
KeywordParallel computingdc.subject
KeywordOptimization problemdc.subject
KeywordUniversal restart strategydc.subject
Dewey Decimal GroupDDC 004 / Data processing & computer sciencedc.subject.ddc
LCSHStatistical analysisdc.subject.lcsh
LCSHComputational complexitydc.subject.lcsh
LCSHMachine learningdc.subject.lcsh
LCSHComputer algorithmsdc.subject.lcsh
TitleRestart strategiesdc.title
Resource typeDissertationdc.type
Date of acceptance2021-07-26dcterms.dateAccepted
RefereeSchöning, Uwedc.contributor.referee
RefereeSteger, Angelikadc.contributor.referee
RefereeTorán, Jacobodc.contributor.referee
DOIhttp://dx.doi.org/10.18725/OPARU-41185dc.identifier.doi
PPN1787281728dc.identifier.ppn
URNhttp://nbn-resolving.de/urn:nbn:de:bsz:289-oparu-41261-6dc.identifier.urn
GNDStatistische Analysedc.subject.gnd
GNDBerechnungskomplexitätdc.subject.gnd
GNDMaschinelles Lernendc.subject.gnd
GNDAlgorithmusdc.subject.gnd
FacultyFakultät für Ingenieurwissenschaften, Informatik und Psychologieuulm.affiliationGeneral
InstitutionInstitut für Theoretische Informatikuulm.affiliationSpecific
Grantor of degreeFakultät für Ingenieurwissenschaften, Informatik und Psychologieuulm.thesisGrantor
DCMI TypeTextuulm.typeDCMI
CategoryPublikationenuulm.category
Bibliographyuulmuulm.bibliographie


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record