2 papers
cs.DS2014
Online Multi-Coloring with Advice
Marie G. Christ, Lene M. Favrholdt, Kim S. Larsen
We consider the problem of online graph multi-coloring with advice. Multi-coloring is often used to model frequency allocation in cellular networks. We give several nearly tight up…
cs.DS2013
Online Bin Covering: Expectations vs. Guarantees
Marie G. Christ, Lene M. Favrholdt, Kim S. Larsen
Bin covering is a dual version of classic bin packing. Thus, the goal is to cover as many bins as possible, where covering a bin means packing items of total size at least one in t…