Towards Understanding the Performance of Randomized Algorithms

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F16%3A00306647" target="_blank" >RIV/68407700:21240/16:00306647 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Towards Understanding the Performance of Randomized Algorithms

Original language description

EDA tools employ randomized algorithms for their favorable properties. Deterministic algorithms have been found sensitive to details in the input, and thus they also behave as the randomized ones. In both cases, performance analysis and comparison shall be made by histograms, or more precisely, by their probability density distribution. We present a modeling of ABC performance and, to gain understanding, a simple randomized algorithm solving the 3MAX-SAT problem. Also, a simulated annealing algorithm solving the same problem is studied. We claim that Gaussian Mixtures are suitable for such models and that truncated models must be considered.

Czech name

—

Czech description

—

Type

C - Chapter in a specialist book

CEP classification

JC - Computer hardware and software

OECD FORD branch

—

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2016

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Book/collection name

Problems and New Solutions in the Boolean Domain

ISBN

978-1-4438-8947-6

Number of pages of the result

20

Pages from-to

167-186

Number of pages of the book

445

Publisher name

Cambridge Scholars Publishing

Place of publication

Newcastle upon Tyne

UT code for WoS chapter

—