Profit-based latency problems on the line

详细信息    查看全文

• 作者：Sofie Coene ; Frits C.R. Spieksma
• 关键词：Minimum latency ; Traveling repairman ; Dynamic programming ; Complexity
• 刊名：Operations Research Letters
• 出版年：2008
• 出版时间：May 2008
• 年：2008
• 卷：36
• 期：3
• 页码：333-337
• 全文大小：329 K

文摘

We consider a latency problem with a profit coration:none; color:black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V8M-4R7J7YP-1&_mathId=mml1&_user=1067359&_cdi=5874&_rdoc=14&_acct=C000058823&_version=1&_userid=2795313&md5=f4403fc8d7341ffac82d0a074775c949"" title=""Click to view the MathML source"" alt=""Click to view the MathML source"">p_i for each client. When serving a client, a revenue of coration:none; color:black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V8M-4R7J7YP-1&_mathId=mml2&_user=1067359&_cdi=5874&_rdoc=14&_acct=C000058823&_version=1&_userid=2795313&md5=10e361dad13358af4f5d6c636f28c6e1"" title=""Click to view the MathML source"" alt=""Click to view the MathML source"">p_i−t is collected. The goal is to find routes for the servers such that total collected revenue is maximized. We study the complexity of different variants of this problem on the line.