@inproceedings{HillerVredeveld2009, author = {Hiller, Benjamin and Vredeveld, Tjark}, title = {Stochastic dominance analysis of online bin coloring algorithms}, booktitle = {9th Workshop on Models and Algorithms for Planning and Scheduling Problems}, year = {2009}, language = {en} } @article{HillerVredeveld2012, author = {Hiller, Benjamin and Vredeveld, Tjark}, title = {Probabilistic alternatives for competitive analysis}, volume = {27}, journal = {Computer Science - Research and Development}, number = {3}, publisher = {Springer}, doi = {10.1007/s00450-011-0149-1}, pages = {189 -- 196}, year = {2012}, language = {en} } @misc{HillerVredeveld2012, author = {Hiller, Benjamin and Vredeveld, Tjark}, title = {Probabilistic alternatives for competitive analysis}, issn = {1438-0064}, doi = {10.1007/s00450-011-0149-1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15131}, year = {2012}, abstract = {In the last 20 years competitive analysis has become the main tool for analyzing the quality of online algorithms. Despite of this, competitive analysis has also been criticized: It sometimes cannot discriminate between algorithms that exhibit significantly different empirical behavior, or it even favors an algorithm that is worse from an empirical point of view. Therefore, there have been several approaches to circumvent these drawbacks. In this survey, we discuss probabilistic alternatives for competitive analysis.}, language = {en} } @inproceedings{HeinzKrumkeMegowetal.2006, author = {Heinz, Stefan and Krumke, Sven and Megow, Nicole and Rambau, J{\"o}rg and Tuchscherer, Andreas and Vredeveld, Tjark}, title = {The Online Target Date Assignment Problem}, volume = {3879}, booktitle = {Proc. 3rd Workshop on Approximation and Online Algorithms}, editor = {Erlebach, Thomas and Persiano, Giuseppe}, publisher = {Springer}, pages = {230 -- 243}, year = {2006}, language = {en} } @misc{HillerVredeveld2008, author = {Hiller, Benjamin and Vredeveld, Tjark}, title = {Probabilistic analysis of Online Bin Coloring algorithms via Stochastic Comparison}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10726}, number = {08-18}, year = {2008}, abstract = {This paper proposes a new method for probabilistic analysis of online algorithms that is based on the notion of stochastic dominance. We develop the method for the Online Bin Coloring problem introduced by Krumke et al. Using methods for the stochastic comparison of Markov chains we establish the strong result that the performance of the online algorithm GreedyFit is stochastically dominated by the performance of the algorithm OneBin for any number of items processed. This result gives a more realistic picture than competitive analysis and explains the behavior observed in simulations.}, language = {en} } @misc{HarksHeinzPfetschetal.2007, author = {Harks, Tobias and Heinz, Stefan and Pfetsch, Marc and Vredeveld, Tjark}, title = {Online Multicommodity Routing with Time Windows}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9654}, number = {07-22}, year = {2007}, abstract = {We consider a multicommodity routing problem, where demands are released \emph{online} and have to be routed in a network during specified time windows. The objective is to minimize a time and load dependent convex cost function of the aggregate arc flow. First, we study the fractional routing variant. We present two online algorithms, called Seq and Seq\$^2\$. Our first main result states that, for cost functions defined by polynomial price functions with nonnegative coefficients and maximum degree~\$d\$, the competitive ratio of Seq and Seq\$^2\$ is at most \$(d+1)^{d+1}\$, which is tight. We also present lower bounds of \$(0.265\,(d+1))^{d+1}\$ for any online algorithm. In the case of a network with two nodes and parallel arcs, we prove a lower bound of \$(2-\frac{1}{2} \sqrt{3})\$ on the competitive ratio for Seq and Seq\$^2\$, even for affine linear price functions. Furthermore, we study resource augmentation, where the online algorithm has to route less demand than the offline adversary. Second, we consider unsplittable routings. For this setting, we present two online algorithms, called U-Seq and U-Seq\$^2\$. We prove that for polynomial price functions with nonnegative coefficients and maximum degree~\$d\$, the competitive ratio of U-Seq and U-Seq\$^2\$ is bounded by \$O{1.77^d\,d^{d+1}}\$. We present lower bounds of \$(0.5307\,(d+1))^{d+1}\$ for any online algorithm and \$(d+1)^{d+1}\$ for our algorithms. Third, we consider a special case of our framework: online load balancing in the \$\ell_p\$-norm. For the fractional and unsplittable variant of this problem, we show that our online algorithms are \$p\$ and \$O{p}\$ competitive, respectively. Such results where previously known only for scheduling jobs on restricted (un)related parallel machines.}, language = {en} } @misc{HillerVredeveld2012, author = {Hiller, Benjamin and Vredeveld, Tjark}, title = {Stochastic dominance analysis of Online Bin Coloring algorithms}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-16502}, year = {2012}, abstract = {This paper proposes a new method for probabilistic analysis of online algorithms. It is based on the notion of stochastic dominance. We develop the method for the online bin coloring problem introduced by Krumke et al (2008). Using methods for the stochastic comparison of Markov chains we establish the result that the performance of the online algorithm GreedyFit is stochastically better than the performance of the algorithm OneBin for any number of items processed. This result gives a more realistic picture than competitive analysis and explains the behavior observed in simulations.}, language = {en} } @misc{HillerVredeveld2008, author = {Hiller, Benjamin and Vredeveld, Tjark}, title = {On the optimality of Least Recently Used}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10928}, number = {08-39}, year = {2008}, abstract = {It is well known that competitive analysis yields too pessimistic results when applied to the paging problem and it also cannot make a distinction between many paging strategies. Many deterministic paging algorithms achieve the same competitive ratio, ranging from inefficient strategies as flush-when-full to the good performing least-recently-used (LRU). In this paper, we study this fundamental online problem from the viewpoint of stochastic dominance. We show that when sequences are drawn from distributions modelling locality of reference, LRU is stochastically better than any other online paging algorithm.}, language = {en} }