Multi-Objective Quality-Driven Service Selection—A Fully Polynomial Time Approximation Scheme
Multi-Objective Quality-Driven Service Selection—A Fully Polynomial Time Approximation Scheme
复制标题
DOI：
10.1109/tse.2013.61
复制
发表时间：
2014-02
影响因子：
7.4
通讯作者：
Immanuel Trummer;B. Faltings;Walter Binder
中科院分区：
文献类型：
--
作者：
Immanuel Trummer;B. Faltings;Walter Binder
多目标质量驱动的服务选择 (QDSS) 的目标是为服务质量 (QoS) 值是帕累托最优的工作流找到服务选择。我们考虑多种 QoS 属性，例如响应时间、成本和可靠性。如果没有其他选择对于某些属性具有更好的 QoS 值并且对于所有其他属性至少具有相同的值，则该选择是帕累托最优。已经提出了找到所有帕累托最优选择的精确算法。然而，它们的复杂性呈指数级增长。随机算法可以很好地扩展，但不能对结果精度提供任何正式保证。我们提出了 QDSS 的第一个近似方案。它的目标是精确算法和随机算法之间的最佳点：它将多项式复杂性与形式结果精度保证结合起来。参数允许无缝地权衡结果精度和效率。我们正式分析复杂性和精度保证，并通过实验将我们的算法与精确和随机方法进行比较。与精确算法相比，我们的近似方案可以将优化时间从几小时缩短到几秒钟。其近似误差保持在 1.4% 以下，而随机算法接近理论最大值。
The goal of multi-objective quality-driven service selection (QDSS) is to find service selections for a workflow whose quality-of-service (QoS) values are Pareto-optimal. We consider multiple QoS attributes such as response time, cost, and reliability. A selection is Pareto-optimal if no other selection has better QoS values for some attributes and at least equivalent values for all others. Exact algorithms have been proposed that find all Pareto-optimal selections. They suffer however from exponential complexity. Randomized algorithms scale well but do not offer any formal guarantees on result precision. We present the first approximation scheme for QDSS. It aims at the sweet spot between exact and randomized algorithms: It combines polynomial complexity with formal result precision guarantees. A parameter allows to seamlessly trade result precision against efficiency. We formally analyze complexity and precision guarantees and experimentally compare our algorithm against exact and randomized approaches. Comparing with exact algorithms, our approximation scheme allows to reduce optimization time from hours to seconds. Its approximation error remains below 1.4 percent while randomized algorithms come close to the theoretical maximum.