本文研究使用学习增强算法解决在线设施定位问题,在实际数据上验证该算法的性能并与当前最佳在线算法进行比较,结果表明该算法具有不错的竞争比率和适用性。
Jul, 2021
探讨 “移动设施位置” 问题,在公共度量空间中移动设施以减少总体成本,并使用一种基于局部搜索的近似算法,实现任意常数 ε>0 的(3+ε)- 近似度。
Jan, 2013
本文研究具有预测的在线图形问题,提出了一个新的度量误差的定义 (metric error),并给出了一个通用框架,用于在线预测算法。采用这个框架,我们能够获得关于竞争比率的紧密限制,并将其作为度量误差的函数来描述。
Dec, 2021
研究多阶段设施重新分配问题,包括在离线和在线两种情况下算法的设计和性能证明,提出了一种可实行的策略证明机制并给出最优性证明。
Mar, 2021
本文研究了度量实例的本地搜索算法,针对设备位置问题:无容量设备位置问题(UFL),以及 $k$-median,$k$-center 和 $k$-means 的无容量版本。
Sep, 2008
本文提出一种针对多个资源分配问题的算法体系,将在线请求建模为每次从未知的概率分布中独立抽取,给出了一个在任意接受数据的情况下获得一定比例最优解的单一算法,并且探究了如何在任意情况下应对敌对分布。同时,文中提出了解决大型 LPs 混合装填覆盖问题的快速算法,并分析了该算法在在线拍卖、网络路由和广告策略方案等特殊情况下的应用。
Mar, 2019
使用时间依赖动态设施定位问题来研究不断演变的网络,该模型强调主体关系的突发变化,而不是持续演变的基础网络。我们提供的近似算法可获得更好的拟合解。
Mar, 2014
本文探讨了在给定区域中通过找到最优解决方案来最小化平均距离的经典最优设施选址问题,并比较了一次性放置全部点和逐步添加的两种策略在解决最优解决方案时的渐近行为,发现它们展现出不同的性质,不过,在两种方法下,优化成本的渐近次序相同。
Dec, 2006
本文研究预约服务的 Web 和移动应用程序,针对该类问题提出了带性能保证的新算法,并在纽约市卫生系统的预约数据上进行了测试。
May, 2018
在一维设置中考虑设施位置问题及算法和机制设计的视角。从算法设计的角度出发,证明了相应的优化问题是 NP 难问题,但是在限制设施数量或设施容量完全相同时可以在多项式时间内计算出最优解。从机制设计的角度出发,提出一些新方法提高了策略性,并且获得了接近下限的近似保证。
Nov, 2019