Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/17547
DC FieldValue
dc.titleM2ICAL: A technique for analyzing imperfect comparison algorithms using Markov chains
dc.contributor.authorOON WEE CHONG
dc.date.accessioned2010-07-13T18:00:40Z
dc.date.available2010-07-13T18:00:40Z
dc.date.issued2007-10-16
dc.identifier.citationOON WEE CHONG (2007-10-16). M2ICAL: A technique for analyzing imperfect comparison algorithms using Markov chains. ScholarBank@NUS Repository.
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/17547
dc.description.abstractPractical optimization problems are often not well-defined, in the sense that the quality of a solution cannot be easily calculated. Many algorithms that attempt to solve such problems are comparison-based, i.e., they have a comparison function that compares two (or more) solutions and returns the superior one. Due to the difficulty in calculating the quality of a solution, the comparison function employed is imperfect (i.e., it may make an error). This thesis describes a 4-step process to model imperfect comparison algorithms into Markov Chains, using Monte Carlo simulations to handle the effects of comparison errors. We call this process the Monte Carlo Markov Chain for Imperfect Comparison ALgorithms method, or the M2ICAL method for short. Information that can be extracted from the model include the estimated solution quality after t iterations; the standard deviation of the solutions' quality; and the time to convergence.
dc.language.isoen
dc.subjectAlgorithm Analysis, Markov Chains, Monte Carlo Simulations
dc.typeThesis
dc.contributor.departmentCOMPUTER SCIENCE
dc.contributor.supervisorHENZ, MARTIN J
dc.description.degreePh.D
dc.description.degreeconferredDOCTOR OF PHILOSOPHY
dc.identifier.isiutNOT_IN_WOS
Appears in Collections:Ph.D Theses (Open)

Show simple item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
OonWC.pdf1.17 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

384
checked on Jun 22, 2019

Download(s)

238
checked on Jun 22, 2019

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.