Home| Contact Us| New Journals| Browse Journals| Journal Prices| For Authors|

Print ISSN:
Online ISSN:


  About JIO
  DLINE Portal Home
Home
Aims & Scope
Editorial Board
Current Issue
Next Issue
Previous Issue
Sample Issue
Upcoming Conferences
Self-archiving policy
Alert Services
Be a Reviewer
Publisher
Paper Submission
Subscription
Contact us 		 
  How To Order
  Order Online
Price Information
Request for Complimentary
Print Copy
 
  For Authors
  Guidelines for Contributors
Online Submission
Call for Papers
Author Rights 		 
 
RELATED JOURNALS
Journal of Digital Information Management (JDIM)
Journal of Multimedia Processing and Technologies (JMPT)
International Journal of Web Application (IJWA)

 
 
Progress in Systems and Telecommunication Engineering
 

The Las Vegas Method of Parallelization
Bogdan Zavalnij
Institute of Mathematics and Informatics University of Pecs Ifjusag utja 6, H-7634 Pecs, Hungary
Abstract: While the methods of parallelizing Monte Carlo algorithms in engineering modeling very popular, these methods are of little use in discrete optimization problems. We propose that the variance of the Monte Carlo method, the Las Vegas method can be used for these problems. We would like to outline the basic concept and present the algorithm working on a specific problem of finding the maximum clique.
Keywords: Parallelization, Montecarlo algorithms, Discrete optimization The Las Vegas Method of Parallelization
DOI:
Full_Text   PDF 181 KB   Download:   305  times
References:
[1] Hammersley, J.M. and Handscomb, D.C. Monte Carlo Methods. London. 1975. (1964).
[2] Babai, L. Monte-Carlo algorithms in graph isomorphism testing. Université de Montréal, D.M.S. No.79–10. http:// people.cs.uchicago.edu/~laci/lasvegas79.pdf
[3] Bogdanova, G.T., Brouwer, A.E., Kapralov, S.N. and Ostergaard, P.R.J. Error-Correcting Codes over an Alphabet of Four Elements. Designs, Codes and Cryptography. August 2001, Volume 23, Issue 3, pp 333–342.
[4] Bomze, I.M., Budinich, M., Pardalos, P.M. and Pelillo, M. (1999). The Maximum Clique Problem. In D.-Z. Du and P.M. Pardalos (Eds.) Handbook of Combinatorial Optimization. (pp. 1–74.) Kluwer Academic Publishers.
[5] DIMACS. ftp://dimacs.rutgers.edu/pub/challenge/graph/ (May 30, 2014)
[6] Hasselberg, J., Pardalos, P.M. and Vairaktarakis, G. Test case generators and computational results for the maximum clique problem. Journal of Global Optimization. (1993), 463–482.
[7] Luby, M. and Ertel, W. Optimal Parallelization of Las Vegas Algorithms. In Enjalbert, P at all. (Eds.), Lecture Notes in Computer Science. (1994). (pp. 461–474.) Springer Berlin Heidelberg.
[8] Luby, M., Sinclair, A. and Zuckerman, D. Optimal Speedup of Las Vegas Algorithms. In: Proceedings of the 2nd Israel Symposium on Theory of Computing and Systems. Jerusalem, Israel, June 1993.
[9] Ostergaard, P.R.J. A fast algorithm for the maximum clique problem. Discrete Applied Mathematics. (2002), 197–207.
[10] Szabo, S. Parallel algorithms for finding cliques in a graph. Journal of Physics: Conference Series Volume 268, Number 1. 2011 J. Phys.: Conf. Ser. 268 012030 doi:10.1088/1742-6596/268/1/012030.
[11] Szabo, S. Monotonic matrices and clique search in graphs. Annales Univ. Sci. Budapest., Sect. Comp. (2013), 307–322.
[12] Sloan, N. http://neilsloane.com/doc/graphs.html (May 30, 2014)
[13] Truchet, C., et al. Prediction of Parallel Speed-ups for Las Vegas Algorithms. http://arxiv.org/abs/1212.4287 2012.
[14] Zavalnij, B. Three Versions of Clique Search Parallelization. Journal of Computer Science and Information Technology. June 2014, Vol. 2, No. 2, pp. 09–20.

Home | Aim & Scope | Editorial Board | Author Guidelines | Publisher | Subscription | Previous Issue | Contact Us |Upcoming Conferences|Sample Issues|Library Recommendation Form|

 

Copyright © 2011 dline.info