With growing emphasis on e-commerce marketplace platforms where we have a central platform mediating between the seller and the buyer, it becomes important to keep a check on the availability and profitability of the central store. A store serving too less clients can be non-profitable and a store getting too many orders can lead to bad service to the customers which can be detrimental for the business. In this paper, we study the facility location problem(FL) with upper and lower bounds on the number of clients an open facility serves. Constant factor approximations are known for the restricted variants of the problem with only the upper bounds or only the lower bounds. The only work that deals with bounds on both the sides violates both the bounds [8]. In this paper, we present the first (constant factor) approximation for the problem violating the upper bound by a factor of (5/2) without violating the lower bounds when both the lower and the upper bounds are uniform. We first give a tri-criteria (constant factor) approximation violating both the upper and the lower bounds and then get rid of violation in lower bounds by transforming the problem instance to an instance of capacitated facility location problem.


翻译:随着对电子商务市场平台的日益重视,即我们在卖方和买方之间设有一个中央平台的电子商务市场平台,对中央商店的可用性和盈利性进行检查就变得十分重要。服务过少的商店可能无利可图,而收到过多订单的商店可能会给客户带来不良服务,而这种服务对商业有害。在本文中,我们研究了设施位置问题,即开放设施所服务的客户数量有上下限限制;对问题限量变量的常数系数近似度是已知的,只有上限或下限。关于双方界限的唯一工作违反了这两个界限[8]。在本文件中,我们提出了第一个(固定因素)近似的问题,即违反一个因素(5/2),而当下限和上限设施都一致时,不违反下限的下限。我们首先给出一个三标准(固定因素)近似值,即违反上限和下限,然后通过将问题实例转换成一个已设电站的地点问题实例,从而消除下限的违规行为。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
计算机 | 国际会议信息5条
Call4Papers
3+阅读 · 2019年7月3日
计算机 | 中低难度国际会议信息8条
Call4Papers
9+阅读 · 2019年6月19日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
人工智能 | COLT 2019等国际会议信息9条
Call4Papers
6+阅读 · 2018年9月21日
计算机类 | 国际会议信息7条
Call4Papers
3+阅读 · 2017年11月17日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年8月26日
Arxiv
0+阅读 · 2021年8月26日
Arxiv
0+阅读 · 2021年8月25日
VIP会员
相关资讯
计算机 | 国际会议信息5条
Call4Papers
3+阅读 · 2019年7月3日
计算机 | 中低难度国际会议信息8条
Call4Papers
9+阅读 · 2019年6月19日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
人工智能 | 国际会议信息10条
Call4Papers
5+阅读 · 2018年12月18日
人工智能 | COLT 2019等国际会议信息9条
Call4Papers
6+阅读 · 2018年9月21日
计算机类 | 国际会议信息7条
Call4Papers
3+阅读 · 2017年11月17日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员