<div class="csl-bib-body">
<div class="csl-entry">Iurlano, E. (2022). <i>Scrambling permutations and related structures : Asymtotics and constructions</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2022.102263</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2022.102263
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/101832
-
dc.description.abstract
Eine Familie von Permutationen der symmetrischen Gruppe S_n heißt k-scrambling, falls zu jeder beliebigen Abfolge paarweise verschiedenener Positionen (p_1,...,p_k) eine Permutation existiert, deren Auswertung in p_1 minimal unter den restlichen Auswertungen in p_j ist. Die speziellere Eigenschaft vollständig k-scrambling zu sein, erfordert darüber hinaus, dass die sukzessiven Auswertungen in p_1,...,p_k eine monoton steigende Folge bilden. Familien, die zusätzlichen Verschärfungen letzterer beider Eigenschaften genügen, nennt man k-restricted min-wise independent bzw. stimmen im zweiteren, stärkeren Fall (bis auf isomorphe Identifikation) mit Perfect Sequence Covering Arrays (PSCAs) der Stärke k überein. Die Bestimmung von Permutationsfamilien, die diesen unterschiedlich starken Eigenschaften genügen und möglichst kleine (oder gar minimal mögliche) Kardinalität besitzen, ist nicht-trivial und von großer Bedeutung für andere mathematische Richtungen (Ordnungstheorie, Geometrie, Graphentheorie etc.) sowie für eine Vielzahl praktischer Anwendungen wie etwa automatisiertes Testing von Software und schnelle Ähnlichkeitsschätzung von Dokumenten für Suchmaschinen. Wir analysieren das asymptotische Verhalten dieser kleinstmöglichen Kardinalitäten und befassen uns auch mit algorithmischen Zugängen, um solche Familien explizit zu konstruieren. Hierbei gelingt es uns eine offene Frage von R. Yuster nach der polynomialen Beschränktheit der Größen von PSCAs [Yus20] positiv zu beantworten; wir erhalten außerdem verbesserte asymptotische untere Schranken sowie für k=3 und k=4 verbesserte asymptotische obere Schranken. Auch im nicht-asymptotischen Bereich – also für konkrete, kleine Werte von n – erreichen wir für k=3 und k=4 einige Verbesserungen (bis zu Faktor 7.5 im Vergleich zum derzeit verfügbaren State of the art in der Literatur). Abschließend schlagen wir eine neue Klasse von Permutationsfamilien vor, die einer gewissen Spiegelungssymmetrie genügen, und nutzen sie zur Ausdünnung des Suchraumes, der überprüft werden muss, um PSCAs computergestützt systematisch via Backtracking zu suchen. Diese Klasse könnte womöglich nützlich sein, um mit ausreichend Rechenleistung künftig weitere Verbesserungen im nicht-asymptotischen Bereich zu erzielen.
de
dc.description.abstract
A family of permutations of the symmetric group S_n is called k-scrambling if for any sequence of pairwise distinct positions (p_1,...,p_k) there exists a permutation whose evaluation in p_1 is minimal among the remaining evaluations in p_j. Moreover, the more special property of being completely k-scrambling requires that the successive evaluations in p_1,...,p_k form a monotonically increasing sequence. Families satisfying additional sharpenings of the latter two properties are k-restricted min-wise independent or, in the second, stronger case coincide (up to isomorphic identification) with perfect sequence covering arrays (PSCAs) of strength k. Determining permutation families that satisfy these differently strong properties and have small (or even minimal possible) cardinality is non-trivial and of great importance for other mathematical branches (order theory, geometry, graph theory, etc.) as well as for a variety of practical applications such as automated testing of software and fast similarity estimation of documents for web search engines. We analyze the asymptotic behavior of these smallest possible cardinalities and also address algorithmic approaches to construct such families explicitly. Here we succeed in answering positively an open question of R. Yuster on the polynomial boundedness of the cardinalities of PSCAs [Yus20]; we also obtain improved asymptotic lower bounds and for k=3 and k=4 improved asymptotic upper bounds. Even in the non-asymptotic range – i.e., for concrete, small values of n – we achieve some improvements for k=3 and k=4 (up to a factor of 7.5 compared to the currently available state of the art in the literature). Finally, we propose a new class of permutation families that satisfy a certain reflection symmetry, and use it to restrict the search space that needs to be scanned in order to computationally seek PSCAs systematically via backtracking. This class could potentially be useful to achieve further improvements in the non-asymptotic range in the future with sufficient computational power.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
k-scrambling permutations
en
dc.subject
sequence covering arrays
en
dc.subject
combinatorial software testing
en
dc.subject
combinatorial designs
en
dc.title
Scrambling permutations and related structures : Asymtotics and constructions
en
dc.title.alternative
Scrambling Permutationen und verwandte Strukturen : Asymptotik and Konstruktionen
de
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.identifier.doi
10.34726/hss.2022.102263
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Enrico Iurlano
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E104 - Institut für Diskrete Mathematik und Geometrie
-
dc.type.qualificationlevel
Diploma
-
dc.identifier.libraryid
AC16679718
-
dc.description.numberOfPages
95
-
dc.thesistype
Diplomarbeit
de
dc.thesistype
Diploma Thesis
en
tuw.author.orcid
0000-0001-7528-0834
-
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
tuw.advisor.staffStatus
staff
-
item.openairetype
master thesis
-
item.fulltext
with Fulltext
-
item.cerifentitytype
Publications
-
item.openaccessfulltext
Open Access
-
item.mimetype
application/pdf
-
item.languageiso639-1
en
-
item.openairecristype
http://purl.org/coar/resource_type/c_bdcc
-
item.grantfulltext
open
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity