Competitive Analysis for Multi-objective Online Algorithms
作者： Morten Tiedemann , Jonas Ide , Anita Schöbel
DOI: 10.1007/978-3-319-15612-5_19
关键词:
摘要: So far, the concept of competitive analysis for online problems is in general applied to single-objective problems. However, many can be extended multi-objective a natural way, but uniform theory these not provided literature. We expand and achieve consistent framework Furthermore, we analyze time series search problem present deterministic algorithms with best possible ratios.
springer.com
sci-hub.st 参考文章(10)
Rajeev Motwani, Eric Torng, Steven J. Phillips, Non-Clairvoyant Scheduling. Theoretical Computer Science. ,vol. 130, pp. 17- 47 ,(1994)
Ran El-Yaniv, Allan Borodin, Online Computation and Competitive Analysis ,(1998)
E. Torng, J. Wein, C. Stein, C.A. Phillips, Optimal time-critical scheduling via resource augmentation 29. annual ACM symposium on the interface: computing science and statistics, El Paso, TX (United States), 4-17 May 1997. ,(1997)
Cristina Bazgan, Laurent Gourvès, Jérôme Monnot, Approximation with a Fixed Number of Solutions of Some Biobjective Maximization Problems Approximation and Online Algorithms. pp. 233- 246 ,(2012) , 10.1007/978-3-642-29116-6_20
Bala Kalyanasundaram, Kirk Pruhs, Speed is as powerful as clairvoyance Journal of the ACM. ,vol. 47, pp. 617- 643 ,(2000) , 10.1145/347476.347479
Cynthia A. Phillips, Cliff Stein, Eric Torng, Joel Wein, Optimal time-critical scheduling via resource augmentation (extended abstract) symposium on the theory of computing. pp. 140- 149 ,(1997) , 10.1145/258533.258570
Thomas Erlebach, Hans Kellerer, Ulrich Pferschy, Approximating Multiobjective Knapsack Problems web science. ,vol. 48, pp. 1603- 1612 ,(2002) , 10.1287/MNSC.48.12.1603.445
R. El-Yaniv, A. Fiat, R. M. Karp, G. Turpin, Optimal Search and One-Way Trading Online Algorithms Algorithmica. ,vol. 30, pp. 101- 139 ,(2001) , 10.1007/S00453-001-0003-0
Matthias Ehrgott, Multicriteria Optimization ,(2005)
Rajeev Motwani, Steven Phillips, Eric Torng, Nonclairvoyant scheduling Theoretical Computer Science. ,vol. 130, pp. 17- 47 ,(1994) , 10.1016/0304-3975(94)90151-1