Efficient Randomized Algorithms for Graph Theoretic Applications

Abstract

Randomization is currently one of the major approaches which is used to design algorithms. A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic. A randomized algorithm uses random input in the hope of achieving good performance in an average case. In addition to input, algorithm takes a source of random numbers and makes random choices during the execution. Its behavior may vary even on a fixed input. This thesis provides comprehensive and integrated analysis of randomized algorithms over deterministic algorithms. We have also discussed the detailed literature of the multiobjective shortest path problem and multiobjective spanning tree problem. Deterministic polynomial time algorithms are extensively used for the shortest path and the minimum spanning tree problems. In this thesis, we have presented a randomized algorithm to find Hamiltonian circuit in rectangular grid graphs with vertical size m and horizontal size n. The algorithm firstly finds all the restricted edges in linear time and then constructs a Hamiltonian circuit by joining the sub-graphs. Algorithm uses random selection to construct the Hamiltonian cycle. The computational model is a unit cost random access machine with the restriction that only binary operation is allowed on edge selection. Load balancing is extensively used in distributed network applications to decrease the response times. We have also discussed the backend load balancing (processor-to-dispatcher). Many algorithms are devised for front end load balancing e.g. JSQ, SQ(d) and JIQ. Join-Idle-Queue(JIQ) goes well in a distributed environment like cloud computing. In JIQ approach, at the backend, a processor joins the queue on either random or sampled basis. In both the cases, I-Queue of any dispatcher might remain empty, resulting in degrading the performance. After finishing the job, the processor should join the dispatcher whose I-Queue is empty. To achieve this, we have used a dequeue to track the dispatcher with empty I-Queue. As the processor finishes the current job and reaches the idle state, it should refer the dequeue and join the dispatcher whose I-Queue is empty.