May, 2018

面向带客户偏好的服务在线提前预定调度

PDF
TL;DR本文研究预约服务的 Web 和移动应用程序，针对该类问题提出了带性能保证的新算法，并在纽约市卫生系统的预约数据上进行了测试。
web and mobile applicationsschedulingweighted bipartite matching problemsperformance analysisappointment scheduling
发现论文，激发创造
  • 在线随机匹配，泊松到达和自然线性规划

    研究在线随机匹配问题，提出了基于 Poisson 到达模型的 0.711 竞争性算法和近似等价性证明，应用线性规划和 Jensen 不等式实现算法优化，推出第一个在较弱随机到达模型下的节点加权在线随机匹配算法。

    Mar, 2021

  • 在线随机匹配：新算法和界限

    本文提出了一些基本的算法变体和改进，旨在提高已知 IID 模型和具有随机奖励延伸的模型的竞争比率，另外提出了加强型线性规划基准来提高非加权边的概率的情况。

    Jun, 2016

  • 非静态客户的在线资源分配

    我们提出了一种新颖的算法，用于在线资源分配，适用于非平稳的用户到达和未知的点击率。

    Jan, 2024

  • 资源分配问题的近最优在线算法和快速近似算法

    本文提出一种针对多个资源分配问题的算法体系，将在线请求建模为每次从未知的概率分布中独立抽取，给出了一个在任意接受数据的情况下获得一定比例最优解的单一算法，并且探究了如何在任意情况下应对敌对分布。同时，文中提出了解决大型 LPs 混合装填覆盖问题的快速算法，并分析了该算法在在线拍卖、网络路由和广告策略方案等特殊情况下的应用。

    Mar, 2019

  • 两个世界中的最佳选择：在未知到达模型下的在线资源分配与预测

    给定未知质量的预测作为输入，我们提出了一种算法，在未知预测质量和请求模型的情况下，在在线资源分配问题中实现了渐进最优表现，验证了算法的性能与任何已知到达模型和预测准确性的算法的最佳性能相匹配。

    Feb, 2024

  • 在线顶点加权二分匹配：通过随机到达击败 1-1/e

    介绍一种加权排名算法，对于在线顶点以随机顺序到达时的顶点加权二分匹配问题证明了 0.6534 的竞争比率。基于 Devanur 等人的随机原始对偶框架，设计了一个二维收益共享函数来提高算法的竞争比率，并在在线二分匹配问题中达到了大于 1-1 /e 的拓展比率。

    Apr, 2018

  • 预测调度

    探讨利用机器学习算法进行医学影像诊断的问题，并提出在线调度问题的解决方案，通过分析来自不同紧迫性病人的数据，制定出优先顺序以提高病人救治效率。

    Dec, 2022

  • 在线随机匹配：超越 1-1/e

    本研究介绍了一种算法来解决在线随机二分匹配问题，提供了一个 0.67 的逼近比和一种基于流量图和最大流问题的新方法来解决这个问题。

    May, 2009

  • 共乘平台中的分配问题：在线匹配与离线可重复使用资源

    这篇论文提出了一种新的在线匹配模型，该模型考虑了资源重用问题，同时给出了一个基于线性规划的自适应算法，可以在应用实例如出租车调度服务等中得到应用。

    Nov, 2017

  • 具有长期约束的随机网络资源分配的在线优化

    本文研究了一个在线资源预订问题，通过一个由两个计算节点组成的通信网络，在有限时间内最小化整体预订成本，并且保持累计违规与运输成本在一定预算限制下的在线重复博弈，提出了一个在线鞍点算法来解决该问题。

    May, 2023