- ICML在线带有有限指导的二部图匹配
研究在线非加权二分图匹配中的问题,其中有 n 个离线顶点和 n 个在线顶点,并且希望与最佳离线算法保持竞争力。尽管 Karp 等人 [1990] 的经典 RANKING 算法可以证明达到 1-1/e>1/2 的竞争比率,但我们表明在对抗性到 - 能效调度与预测
在能效调度中,使用学习增强的算法框架,通过减小预测误差,实现多种能效调度问题的竞争比率改善。
- 非静态客户的在线资源分配
我们提出了一种新颖的算法,用于在线资源分配,适用于非平稳的用户到达和未知的点击率。
- 具有切换成本和延迟梯度的在线凸优化
在线凸优化问题中,我们考虑带有二次和线性切换成本的有限信息环境下的问题,通过使用关于先前目标函数的梯度信息,我们提出了在线多梯度下降算法 (Online Multiple Gradient Descent, OMGD),并证明了其在二次切换 - AAAI一种改进的在线最小和集合覆盖算法
本文探讨基于在线偏好聚合的基础模型,在评估算法的竞争力方面提出了一种新算法,能够实现更强的动态最优解,算法的竞争比由 $O (r^2)$ 到达。
- 在最大化收益的同时减少不平等:改进赌博算法的紧密任何时刻保证
研究改进多臂老虎机(IMAB)问题在未来奖励不确定的情况下,如何使决策者在考虑潜在长期回报时最大化当前累计奖励,并提出了一种算法来解决此问题,并证明其近似最优。
- 在线图算法预测
本文研究具有预测的在线图形问题,提出了一个新的度量误差的定义 (metric error),并给出了一个通用框架,用于在线预测算法。采用这个框架,我们能够获得关于竞争比率的紧密限制,并将其作为度量误差的函数来描述。
- AAAI在线斯坦纳树学习增强算法
本文考虑了将机器学习与在线算法设计相结合的新型 “超越最坏情况” 算法分析模型在在线 Steiner 树问题上的应用,其中预测的终端节点可能不正确,算法性能取决于错误预测的数量,可以通过正确预测来突破在线下界并且具有良好的竞争比,同时实验证 - 学习增强的在线设施选址
本文研究使用学习增强算法解决在线设施定位问题,在实际数据上验证该算法的性能并与当前最佳在线算法进行比较,结果表明该算法具有不错的竞争比率和适用性。
- 具有不确定加工时间的流程时间调度
本文提出了一种在线调度算法,可以在不知道任务精确处理时间的情况下解决加权流时间问题,并且可以通过给定的预测时间匹配知名度与权重关系,算法具有鲁棒性。
- MM网络容量扩展辅以不可靠机器学习预测
本文介绍了一种名为 Adaptive Balanced Capacity Scaling (ABCS) 的算法,该算法能够通过使用基于机器学习的预测来适应并减小数据中心的能耗和交换成本,同时保持足够的预测精度和竞争比率,相关的实验结果也证明 - 在线多容量打车的竞争比率
本研究提出了在在线多容量拼车中具有竞争比率边界的方法,以解决由三部分图形成的匹配问题,该问题包括资源、请求和请求组以减少碳排放和提供更高的车辆 / 资源收入。
- 线上搜寻提示
该研究考虑了在给定提示的情况下,在线性搜索问题中如何最小化搜寻者走过的路程与目标位置的距离之比,并探讨了不同类型提示下的搜索策略及其 Pareto 效率。
- 基于机器学习建议的在线页面迁移
研究了使用预测方法改善其性能的在线算法在页面迁移问题上的应用,通过机器学习实现预测精度提高,可实现竞争比接近 1,为算法改进方法的新领域提供了有益的探讨。
- 基于机器学习建议的秘书问题和在线匹配问题
通过机器学习算法,结合在线算法,可以提高选择问题中的服务质量,并且能够在预测准确的情况下最大化竞争力。
- 关于树、单圈图和仙人掌图的在线图探索
探究搜索者搜索未知的加权无向图的问题,证明最近邻算法的竞争比率在树中为 θ(logn),并研究参数范围内算法 Blocking 在单轮图上是 3-competitive,在仙人掌图上是 5/2+√2 约等于 3.91-competitive - 图探索竞争问题的改进下界
通过访问顶点并返回起始位置的单一代理器的边权无向图探索,我们在 competitive ratio 上获得了 10/3 的改进下界,这与 Dobrev 的下限相比较,也适用于平面图。
- 在线可重用资源的渐进最优竞争比率分配
研究了在线分配问题,通过创建不对称性来控制重用性引起的随机依赖,并建立了一个新算法,获得了最佳竞争比率。(The paper studies the problem of online allocation and proposes a n - 使用预测和非凸损失的在线优化
本文提出了两个有效的充分条件来解决在线非凸优化和运动成本问题,并得出了算法 SFHC 的竞争比率,并且还为运动和击打成本提供了竞争比率结果。
- 机器学习建议在线缓存的近最优界限
该论文研究了基于机器学习建议的在线缓存模型,提出了一种新的算法来解决缓存问题,该算法适用于低误差情况下的预测,具有低的竞争比率;通过改进算法和提供下限,有望进一步提高算法性能。