000199070 001__ 199070
000199070 005__ 20181203023512.0
000199070 0247_ $$2doi$$a10.1109/Tse.2013.61
000199070 022__ $$a0098-5589
000199070 02470 $$2ISI$$a000334666000005
000199070 037__ $$aARTICLE
000199070 245__ $$aMulti-Objective Quality-Driven Service Selection-A Fully Polynomial Time Approximation Scheme
000199070 260__ $$aLos Alamitos$$bInstitute of Electrical and Electronics Engineers$$c2014
000199070 269__ $$a2014
000199070 300__ $$a25
000199070 336__ $$aJournal Articles
000199070 520__ $$aThe 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.
000199070 6531_ $$aQuality-driven service selection
000199070 6531_ $$amulti-objective optimization
000199070 6531_ $$aapproximation algorithms
000199070 700__ $$0243342$$aTrummer, Immanuel$$g194778$$uEcole Polytech Fed Lausanne, Artificial Intelligence Lab, CH-1015 Lausanne, Switzerland
000199070 700__ $$0240959$$aFaltings, Boi$$g105074$$uEcole Polytech Fed Lausanne, Artificial Intelligence Lab, CH-1015 Lausanne, Switzerland
000199070 700__ $$0241254$$aBinder, Walter$$g157488
000199070 773__ $$j40$$k2$$q167-191$$tIeee Transactions On Software Engineering
000199070 909C0 $$0252184$$pLIA$$xU10406
000199070 909CO $$ooai:infoscience.tind.io:199070$$pIC$$particle
000199070 917Z8 $$x208605
000199070 937__ $$aEPFL-ARTICLE-199070
000199070 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000199070 980__ $$aARTICLE