In online interval scheduling, the input is an online sequence of intervals, and the goal is to accept a maximum number of non-overlapping intervals. In the more general disjoint path allocation problem, the input is a sequence of requests, each involving a pair of vertices of a known graph, and the goal is to accept a maximum number of requests forming edge-disjoint paths between accepted pairs. These problems have been studied under extreme settings without information about the input or with error-free advice. We study an intermediate setting with a potentially erroneous prediction that specifies the set of intervals/requests forming the input sequence. For both problems, we provide tight upper and lower bounds on the competitive ratios of online algorithms as a function of the prediction error. For disjoint path allocation, our results rule out the possibility of obtaining a better competitive ratio than that of a simple algorithm that fully trusts predictions, whereas, for interval scheduling, we develop a superior algorithm. We also present asymptotically tight trade-offs between consistency (competitive ratio with error-free predictions) and robustness (competitive ratio with adversarial predictions) of interval scheduling algorithms. Finally, we provide experimental results on real-world scheduling workloads that confirm our theoretical analysis.
翻译:在在线间距列表中,输入是一个在线间隔序列,目标是接受最大数量的非重叠间隔。 在更普遍的脱节路径分配问题中,输入是一系列请求,每个请求都涉及一对已知图表的脊椎,目标是接受最大数量的请求,形成被接受的对配之间的分错路径。这些问题是在极端情况下研究的,没有输入信息,也没有提供无误建议。我们研究的是中间设置,其中可能存在错误的预测,规定了构成输入序列的间隔/请求。对于这两个问题,我们提供在线算法竞争比率的严格上限和下限,以作为预测错误的函数。对于脱节路径分配,我们的结果排除了获得比完全相信预测的简单算法更具有竞争力的比率的可能性,而对于时间间隔列表,我们开发了一种更高级的算法。我们还在一致性(与无误预测的竞争性比率)和稳健(与对称的预测的竞争性比率)之间,在时间间隔列表分析中,我们提供了真实的实验性结果。</s>