IMI-BAS BAS
 

BulDML at Institute of Mathematics and Informatics >
ITHEA >
International Journal ITA >
2006 >
Volume 13 Number 3 >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10525/746

Title: Randomized Parallelization – a New Method for Solving Hard Combinatorial Problems
Authors: Zakrevskij, Arkadij
Keywords: Combinatorial Problems
Combinatorial Search
Parallel Computations
Randomization
Run-Time
Acceleration
Issue Date: 2006
Publisher: Institute of Information Theories and Applications FOI ITHEA
Abstract: A new method for solving some hard combinatorial optimization problems is suggested, admitting a certain reformulation. Considering such a problem, several different similar problems are prepared which have the same set of solutions. They are solved on computer in parallel until one of them will be solved, and that solution is accepted. Notwithstanding the evident overhead, the whole run-time could be significantly reduced due to dispersion of velocities of combinatorial search in regarded cases. The efficiency of this approach is investigated on the concrete problem of finding short solutions of non-deterministic system of linear logical equations.
URI: http://hdl.handle.net/10525/746
ISSN: 1313-0463
Appears in Collections:Volume 13 Number 3

Files in This Item:

File Description SizeFormat
ijita13-3-p01.pdf61.05 kBAdobe PDFView/Open

 



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

 

Valid XHTML 1.0!   Creative Commons License DSpace Software Copyright © 2002-2009  The DSpace Foundation - Feedback