• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Offline and online facility leasing
【24h】

Offline and online facility leasing

机译：离线和在线设施租赁

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study the problem of leasing facilities over time, following the general infrastructure leasing problem framework introduced by Anthony and Gupta (2007). If there are K different lease types, Anthony and Gupta give an O(K)-approximation algorithm for the problem. We are able to improve this to a 3-approximation algorithm by using a variant of the primal-dual facility location algorithm of Jain and Vazirani (2001). We also consider the online version of the facility leasing problem, in which the clients to be served arrive over time and are not known in advance. This problem generalizes both the online facility location problem (introduced by Meyerson, 2001) and the parking permit problem (also introduced by Meyerson, 2005). We give a deterministic algorithm for the problem that is O(Klogn)-competitive. No previous result was known for this problem. To achieve our result, we modify an O(logn)-competitive algorithm of Fotakis (2007) for the online facility location problem. We also reanalyze his algorithm via the dual-fitting technique to prove that it achieves the O(log n) competitive ratio.
机译：根据Anthony和Gupta（2007）提出的一般基础设施租赁问题框架，我们研究了随时间推移的租赁设施问题。如果有K个不同的租约类型，则Anthony和Gupta会为该问题提供O（K）近似算法。通过使用Jain和Vazirani（2001）的原始-双重设施定位算法的变体，我们可以将其改进为3近似算法。我们还考虑了设施租赁问题的在线版本，在该版本中，要服务的客户会随着时间的推移而到达，因此事先不知道。这个问题概括了在线设施位置问题（由Meyerson，2001年提出）和停车许可证问题（也由Meyerson，2005年提出）。对于O（Klogn）竞争问题，我们给出了确定性算法。没有以前的结果是已知的此问题。为了获得我们的结果，我们针对在线设施选址问题修改了Fotakis（2007）的O（logn）竞争算法。我们还通过双重拟合技术重新分析了他的算法，以证明该算法达到了O（log n）竞争比。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号