Facility location problems often permit facilities to be located at any position. But what if this is not the case in practice? What if facilities can only be located at particular locations like a highway exit or close to a bus stop? We consider here the impact of such constraints on the location of facilities on the performance of strategy proof mechanisms for locating facilities.We study four different performance objectives: the total distance agents must travel to their closest facility, the maximum distance any agent must travel to their closest facility, and the utilitarian and egalitarian welfare.We show that constraining facilities to a limited set of locations makes all four objectives harder to approximate in general.


翻译:设施定位问题往往允许设施位于任何位置。但如果实际情况并非如此呢?如果设施只能位于高速公路出口或公共汽车站附近等特定地点,怎么办?我们在这里考虑这种设施位置限制对设施定位战略验证机制的实施的影响。我们研究四个不同的绩效目标:总距离代理必须前往最接近的设施,任何代理必须前往最接近的设施的最大距离,以及功利和平等福利。 我们表明,将设施限制在有限的一组地点会使所有四个目标普遍难以接近。

0
下载
关闭预览

相关内容

专知会员服务
34+阅读 · 2021年8月19日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
【CVPR2020】MSG-GAN:用于稳定图像合成的多尺度梯度GAN
专知会员服务
27+阅读 · 2020年4月6日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
已删除
将门创投
5+阅读 · 2019年4月15日
VIP会员
相关VIP内容
专知会员服务
34+阅读 · 2021年8月19日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
【CVPR2020】MSG-GAN:用于稳定图像合成的多尺度梯度GAN
专知会员服务
27+阅读 · 2020年4月6日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
相关资讯
已删除
将门创投
5+阅读 · 2019年4月15日
Top
微信扫码咨询专知VIP会员