Covering selfish machines

Details Covering selfish machines Covering selfish machines

2006-10-05

arxiv.org/abs/cs/0610026v1

Computer Science

Computer Science and Game Theory

Scientific paper

We consider the machine covering problem for selfish related machines. For a constant number of machines, m, we show a monotone polynomial time approximation scheme (PTAS) with running time that is linear in the number of jobs. It uses a new technique for reducing the number of jobs while remaining close to the optimal solution. We also present an FPTAS for the classical machine covering problem (the previous best result was a PTAS) and use this to give a monotone FPTAS. Additionally, we give a monotone approximation algorithm with approximation ratio \min(m,(2+\eps)s_1/s_m) where \eps>0 can be chosen arbitrarily small and s_i is the (real) speed of machine i. Finally we give improved results for two machines. Our paper presents the first results for this problem in the context of selfish machines.

Affiliated with

Also associated with

No associations

Rating

Covering selfish machines does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Covering selfish machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Covering selfish machines will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-656259