Overview

In this

project we describe a very general problem called Hiring problem that can be

used to express a wide variety of different problems. We can use different

algorithm for Hiring problem to solve the different problems like minimum

spanning tree, solving hiring problem etc. We will mainly discuss the setting,

difference between randomized algorithms and probabilistic analysis and how to

code up various problems as Hiring problem at the end, we will brie?y describe

some of the algorithms for solving Hiring problems.

what is Hiring Problem

The problem

discusses the hiring of a candidate from candidates that an employment agency

sends you one each each day. We interview the person and than decide weather to

keep him or not. Each time we hire a candidate we have to fire the previous

one. Interviewing and hiring a candidate cost us some money. The main objective

here is to estimate that how much price does it costs you in order to hire the

best candidate for your office.

Algorithms to solve hiring

problem

How can we

solve hiring problem? The standard algorithm for sloving Hiring problem is

Randomized algorithm. Historically, first randomized algorithm was a function

developed by a person named Michael O.Rabin. This study was further taken in

1977 by Robert M.Solovay and Volker Strassen, and they came up with a

randomized primality test. The after some year Micheal O.Rabin explained that

1977 randomized test can be turned into an algorithm, which after some time was

given a name of Randomized Algorithm. A randomized algorithm is an algorithm

that take randomness as an input or as a part of its operation. It often aims

for major properties like good average case behavior, outputting exact answer

with high probability and getting answers that are very much close to right

answer.

Advantages

Following

are the few advantages of Randomized Algorithms:

Simplicity: Most of randomized

algorithms are simpler than the best algorithms or in other words deterministic

algorithms for the same problem.

Less

Spent time: For

repeated elements the same output by randomized algorithm is more better as

compared to the other deterministic algorithms.

Efficiency:

it performs best for a repeated number of

given time.

Easy

to practice.

Have

also shown to yield improved Complexity bounds.

limitations

Following

are the some limitations of above discussed algorithm:

Hardware

Failure: Max

time with continuous progress can cause a massive hardware failure.

Longer

Runtime: As

these algorithms works in loops, so during a process running, it may split into

continuous parts and causing a longer run time to get final results.

Mass

Space Required: As it a algorithm that works continuously and again and again, it thus

require a lot of storage space on the main memory.

applications

Following

are the few applications of randomized algorithms:

The Birthday Paradox

How many people must there be in a room

before there is a 50% chance that two of them were born on the same day of the

year?

The answer is surprisingly few. The paradox

is that it is in fact far fewer than the number of days in a year, or even half

the number of days in a year.

Balls And Bins.

Consider a process in which

we randomly toss identical balls into b bins,

numbered 1;2; : : : ;b. The tosses are

independent, and on each toss the ball is equally likely to end up in any bin.

The probability that a tossed ball lands in any given bin is 1=b. Thus, the ball-tossing

process is a sequence of Bernoulli trials with a probability 1=b of success, where success

means that the ball falls in the given bin. This model is particularly useful

for analyzing hashing, and we can answer a variety of interesting questions

about tossing ball process.

Streaks

Suppose we flip a coin in air n number of

time. What is the highest possibility of consecutive heads that we can expect to

see? The answer can be given by using this algorithm.

The one line hiring problem

We do not wish to interview

all the candidates in order to find the best one. We also do not wish to hire

and fire as we find better and better applicants. In other words, we are

willing to select for a candidate who is close enough to the best, this in

exchange for hiring exactly once. We must obey one company requirement, so after

each interviewing each candidate we must either immediately offer the job to

the applicant or immediately reject the applicant. What is the trade-off

between minimizing the amount of interviewing and maximizing the quality of the

candidate hired?