Search Content

Post-optimization: necessity analysis for combinatorial arrays

Description

Finding the optimal solution to a problem with an enormous search space can be challenging. Unless a combinatorial construction technique is found that also guarantees the optimality of the resulting solution, this could be an infeasible task. If such a technique is unavailable, different heuristic methods are generally used to…

Finding the optimal solution to a problem with an enormous search space can be challenging. Unless a combinatorial construction technique is found that also guarantees the optimality of the resulting solution, this could be an infeasible task. If such a technique is unavailable, different heuristic methods are generally used to improve the upper bound on the size of the optimal solution. This dissertation presents an alternative method which can be used to improve a solution to a problem rather than construct a solution from scratch. Necessity analysis, which is the key to this approach, is the process of analyzing the necessity of each element in a solution. The post-optimization algorithm presented here utilizes the result of the necessity analysis to improve the quality of the solution by eliminating unnecessary objects from the solution. While this technique could potentially be applied to different domains, this dissertation focuses on k-restriction problems, where a solution to the problem can be presented as an array. A scalable post-optimization algorithm for covering arrays is described, which starts from a valid solution and performs necessity analysis to iteratively improve the quality of the solution. It is shown that not only can this technique improve upon the previously best known results, it can also be added as a refinement step to any construction technique and in most cases further improvements are expected. The post-optimization algorithm is then modified to accommodate every k-restriction problem; and this generic algorithm can be used as a starting point to create a reasonable sized solution for any such problem. This generic algorithm is then further refined for hash family problems, by adding a conflict graph analysis to the necessity analysis phase. By recoloring the conflict graphs a new degree of flexibility is explored, which can further improve the quality of the solution.

ContributorsNayeri, Peyman (Author) / Colbourn, Charles (Thesis advisor) / Konjevod, Goran (Thesis advisor) / Sen, Arunabha (Committee member) / Stanzione Jr, Daniel (Committee member) / Arizona State University (Publisher)

Created2011

Robbie Chan, guitar

ContributorsChan, Robbie (Performer) / McCarrel, Kyla (Performer) / Sadownik, Stephanie (Performer) / ASU Library. Music Library (Contributor)

Created2018-04-18

Joshua Asher Mayo's students; Sarah Betts, Marco Cericola, & Nikolas Gonzalez, classical guitar

ContributorsMayo, Joshua (Contributor) / Betts, Sarah (Performer) / Cericola, Marco (Performer) / Gonzalez, Nikolas (Performer) / ASU Library. Music Library (Publisher)

Created2021-04-28

Manuel M. Ponce's Suite in D major for solo guitar: performance edition and analysis

Description

Whenever a text is transmitted, or communicated by any means, variations may occur because editors, copyists, and performers are often not careful enough with the source itself. As a result, a flawed text may come to be accepted in good faith through repetition, and may often be preferred over the…

Whenever a text is transmitted, or communicated by any means, variations may occur because editors, copyists, and performers are often not careful enough with the source itself. As a result, a flawed text may come to be accepted in good faith through repetition, and may often be preferred over the authentic version because familiarity with the flawed copy has been established. This is certainly the case with regard to Manuel M. Ponce's guitar editions. An inexact edition of a musical work is detrimental to several key components of its performance: musical interpretation, aesthetics, and the original musical concept of the composer. These phenomena may be seen in the case of Manuel Ponce's Suite in D Major for guitar. The single published edition by Peer International Corporation in 1967 with the revision and fingering of Manuel López Ramos contains many copying mistakes and intentional, but unauthorized, changes to the original composition. For the present project, the present writer was able to obtain a little-known copy of the original manuscript of this work, and to document these discrepancies in order to produce a new performance edition that is more closely based on Ponce's original work.

ContributorsReyes Paz, Ricardo (Author) / Koonce, Frank (Thesis advisor) / Solis, Theodore (Committee member) / Rotaru, Catalin (Committee member) / Arizona State University (Publisher)

Created2013