Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

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