• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Integer Programming and Combinatorial 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. 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 . 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) and the parking permit problem (also introduced by Meyerson). We give a deterministic algorithm for the problem that is O(K log n)-competitive. To achieve our result, we modify an O(log n)-competitive algorithm of Fotakis for the online facility location problem.
机译：我们将按照Anthony和Gupta提出的一般基础设施租赁问题框架研究随着时间推移而产生的租赁设施问题。如果有K种不同的租约类型，则Anthony和Gupta会为该问题提供O（K）近似算法。通过使用Jain和Vazirani的原始对偶设施定位算法的变体，我们可以将其改进为3近似算法。我们还考虑了设施租赁问题的在线版本，在该版本中，要服务的客户会随着时间的推移而到达，因此事先未知。该问题将在线设施位置问题（由Meyerson引入）和停车许可证问题（也由Meyerson引入）都推广了。对于O（K log n）竞争问题，我们给出了确定性算法。为了获得我们的结果，我们针对在线设施位置问题修改了Fotakis的O（log n）竞争算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号