Online Multi-Coloring with Advice
From MaRDI portal
Publication:3453285
DOI10.1007/978-3-319-18263-6_8zbMATH Open1329.68297arXiv1409.1722OpenAlexW3003975899MaRDI QIDQ3453285FDOQ3453285
Authors: Marie G. Christ, Kim S. Larsen, Lene M. Favrholdt 
Publication date: 20 November 2015
Published in: Approximation and Online Algorithms (Search for Journal in Brave)
Abstract: 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 upper and lower bounds for the most standard topologies of cellular networks, paths and hexagonal graphs. For the path, negative results trivially carry over to bipartite graphs, and our positive results are also valid for bipartite graphs. The advice given represents information that is likely to be available, studying for instance the data from earlier similar periods of time.
Full work available at URL: https://arxiv.org/abs/1409.1722
Recommendations
- Online multi-coloring with advice
- Advice complexity of the online coloring problem
- scientific article; zbMATH DE number 7758354
- Online hypergraph coloring
- scientific article; zbMATH DE number 65699
- scientific article; zbMATH DE number 1875408
- Advice complexity of online coloring for paths
- Online coloring known graphs
- Three topics in online list coloring
- Online coloring of bipartite graphs with and without advice
Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Title not available (Why is that?)
- Advice complexity of online coloring for paths
- On the advice complexity of the knapsack problem
- On the advice complexity of the set cover problem
- Online coloring of bipartite graphs with and without advice
- On the advice complexity of the \(k\)-server problem
- Information complexity of online problems
- On the Advice Complexity of Online Problems
- Advice complexity of the online coloring problem
- On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
- Advice complexity and barely random algorithms
- Measuring the problem-relevant information in input
- Online computation with advice
- Competitive paging with locality of reference
- On paging with locality of reference
- Competitive snoopy caching
- Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis
- Universal codeword sets and representations of the integers
- Static frequency assignment in cellular networks
- Better bounds for incremental frequency allocation in bipartite graphs
- Channel assignment and weighted coloring
- 1-Local 33/24-Competitive Algorithm for Multicoloring Hexagonal Graphs
- Online multi-coloring on the path revisited
- Distributed Online Frequency Assignment in Cellular Networks
- 2-local <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mn>4</mml:mn><mml:mo stretchy="false">/</mml:mo><mml:mn>3</mml:mn></mml:math>-competitive algorithm for multicoloring hexagonal graphs
- Frequency Allocation Problems for Linear Cellular Networks
- Three results on frequency assignment in linear cellular networks
- Absolute and asymptotic bounds for online frequency allocation in cellular networks
- On the advice complexity of buffer management
- Online bin packing with advice
- On the power of advice and randomization for the disjoint path allocation problem
- The accommodating function: A generalization of the competitive ratio
- Corrigendum: Static frequency assignment in cellular networks
- The seat reservation problem
- Extending the accommodating function
- Online Multi-Coloring with Advice
Cited In (3)
This page was built for publication: Online Multi-Coloring with Advice
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453285)
