Exploring Approximation Algorithms and Their Empirical Analysis by Roger Doss

Author:Roger Doss [Doss, Roger]
Language: eng
Format: azw3
Tags: Dissertation
Publisher: Roger G. Doss
Published: 2016-12-31T16:00:00+00:00

Operational Definition of Variables

Dependent Variables.

Time To. Performance measurement of the optimal solutions was determined by recording timings in microseconds of the algorithms in practice. Timings were recorded using the operating system’s high resolution timers as the algorithms process random input. The variable was measured on a ratio scale.

Time Ta. Performance measurement of the proposed approximations was determined by recording timings in microseconds of the algorithms in practice. Timings were recorded using the operating system’s high resolution timers as the algorithms process random input. The variable was measured on a ratio scale.

M-Vertex Cover Mo. The number of vertices that exist in a given Vertex Cover determines the measurement of how optimal a computed Vertex Cover of a graph is. The number Mo was computed by counting the number of vertices within the set of vertices in the cover as produced by the optimal algorithm. The values ranged from 0 to N-1 vertices. The variable was measured on a ratio scale.

N-Vertex Cover Na. The number of vertices that exist in a given Vertex Cover will determine the measurement of how optimal a computed Vertex Cover of a graph is. The number Na was computed by counting the number of vertices within the set of vertices in the cover as produced by the approximation algorithm. The values ranged from 0 to N-1 vertices. The variable was measured on a ratio scale.

M-Partition Mo. The difference of the cost of the tasks assigned to the two processors determines how optimal a computed Partition is. The number Mo was computed as the difference of the cost of the tasks assigned to the two processors by the optimal algorithm. The value is an integer. The variable was measured on a ratio scale.

N-Partition Na. The difference of the cost of the tasks assigned to the two processors determines how optimal a computed Partition is. The number Na was computed as the difference of the cost of tasks assigned to the two processors by the approximation algorithm. The value is an integer. The variable was measured on a ratio scale.

Average Difference S. For Partition and Vertex Cover, an average based on |Mo-Na| was computed as the measurement of differences from the optimal algorithm. The value is a real number. The variable was measured on a ratio scale.

NrYesOpt Yo. For 3-Satisfiability, the measurement of differences from the optimal algorithm was computed as a formula of ((NrYesOpt - NrYesApprox)/ NrTrials) * 100 where NrTrials is the number of trials and NrYesOpt is the number of yes answers produced by the optimal algorithm. The value is an integer between 0 and NrTrials-1. The variable was measured on a ratio scale.

NrYesApprox Ya. For 3-Satisfiability, the measurement of differences from the optimal algorithm was computed as a formula of ((NrYesOpt - NrYesApprox)/ NrTrials) * 100 where NrTrials is the number of trials and NrYesApprox is the number of yes answers produced by the approximation algorithm. The value is an integer between 0 and NrTrials-1. The variable was measured on a ratio scale.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.