Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison
From MaRDI portal
Publication:3541114
DOI10.1007/978-3-540-87744-8_44zbMath1158.68555OpenAlexW2148693377MaRDI QIDQ3541114
Tjark Vredeveld, Benjamin Hiller
Publication date: 25 November 2008
Published in: Algorithms - ESA 2008 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-87744-8_44
Related Items (7)
Probabilistic quality estimations for combinatorial optimization problems ⋮ Analyzing randomized search heuristics via stochastic domination ⋮ Selfish bin coloring ⋮ Comparing online algorithms for bin packing problems ⋮ On the fastest Vickrey algorithm ⋮ Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison ⋮ Stochastic dominance and the bijective ratio of online algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bounds on the greedy routing algorithm for array networks
- Polynomial time approximation schemes for class-constrained packing problems
- A coupling technique for stochastic comparison of functions of Markov processes
- Average case analysis of bounded space bin packing algorithms
- The relative worst order ratio for online algorithms
- Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison
- Biased Random Walks, Lyapunov Functions, and Stochastic Analysis of Best Fit Bin Packing
- Speed is as powerful as clairvoyance
- Average-case analyses of first fit and random fit bin packing
- Beyond Competitive Analysis
- Markov Paging
- Markov chains, computer proofs, and average-case analysis of best fit bin packing
- Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm
- Algorithms and Computation
- A new average case analysis for completion time scheduling
- On two class-constrained versions of the multiple knapsack problem
This page was built for publication: Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison