2006/10/05 by Leah Epstein, Epstein, Leah, Rob van Stee +1
Computer Science · Decision Sciences · #Auction Theory and Applications #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Optimization and Search Problems #cs.GT
paper · pdf · doi:10.48550/arxiv.cs/0610026
arxiv created 2006/10/05 · openalex publication_date 2006/10/05 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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)s1/sm) where \eps>0 can be chosen arbitrarily small and si 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.