zbMATH — the first resource for mathematics

Online hypergraph coloring with rejection. (English) Zbl 1334.68305
Summary: In this paper we investigate the online hypergraph coloring problem with rejection, where the algorithm is allowed to reject a vertex instead of coloring it but each vertex has a penalty which has to be paid if it is not colored. The goal is to minimize the sum of the number of the used colors for the accepted vertices and the total penalty paid for the rejected ones. We study the online problem which means that the algorithm receives the vertices of the hypergraph in some order \(v_1,\dots,v_n\) and it must decide about \(v_i\) by only looking at the subhypergraph \(H_i = (V_i,E_i)\) where \(V_i=\{v_1,\dots,v_i\}\) and \(E_i\) contains the edges of the hypergraph which are subsets of \(V_i\). We consider two models: in the full edge model only the edges where each vertex is accepted must be well-colored, in the trace model the subsets of the edges formed by the accepted vertices must be well colored as well. We consider proper and conflict free colorings. We present in each cases optimal online algorithms in the sense that they achieve asymptotically the smallest possible competitive ratio.
68W27 Online algorithms; streaming algorithms
05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX Cite
Full Text: DOI
[1] N. Alon, U. Arad, Y. Azar, Independent Sets in Hypergraphs with Applications to Routing Via Fixed Paths, Proc. 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX99), Lecture Notes in Computer Science1671 (1999) 16-27. ⇒8 · Zbl 0949.68172
[2] A. Bar-Noy, P. Cheilaris and S. Smorodinsky, Conflict-free coloring for intervals: from offline to online, Proc. 18th Annual ACM Parallelism Algorithms Architectures (SPAA06), 2006, pp. 128-137. ⇒6 · Zbl 1445.68357
[3] A. Bar-Noy, P. Cheilaris, S. Olonetsky, and S. Smorodinsky, Online conflict-free colorings for hypergraphs, Proc. 34th International Colloquium on Automata, Languages and Programming (ICALP07), Lecture Notes in Computer Science4596 (2007) 219-230. ⇒6 · Zbl 1171.05422
[4] A. Borodin, R. El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998. ⇒6, 8 · Zbl 0931.68015
[5] K. Chen, A. Fiat, H. Kaplan, M. Levy, J. Matousek, E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, U. Wagner and E. Welzl, Online conflict-free coloring for intervals, SIAM J. Computing36 (2006) 1342-1359. ⇒6 · Zbl 1124.68077
[6] K. Chen, H. Kaplan, M. Sharir, Online CF coloring for halfplanes, congruent disks, and axis-parallel rectangles, ACM Trans. Algorithms5 (2009) Article No. 16. ⇒6 · Zbl 1445.68359
[7] L. Epstein, A. Levin, G. J. Woeginger, Graph coloring with rejection, J. Comput. System Sci., 77, 2 (2011) 439-447. ⇒6 · Zbl 1213.05077
[8] M. M. Halldorsson, Online coloring of hypergraphs, Inform. Process. Lett.110, 10 (2010) 370-372. ⇒6 · Zbl 1229.68082
[9] Cs. Imreh, J. Nagy-György, Online hypergraph coloring, Inform. Process. Lett.109, 4 (2008) 23-26. ⇒6 · Zbl 1191.68885
[10] Cs. Imreh, Competitive analysis, in: Algorithms of Informatics, Vol. 1. Foundations (ed. A. Iványi), mondAt Kiadó, Budapest, 2007, pp. 395-428. ⇒6, 8
[11] B. Keszegh, N. Lemons, D. Pálvölgyi, Online and quasi-online colorings of wedges and intervals, Proc. 39th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2013), Lecture Notes in Computer Science7741 (2013) 292-306. ⇒6 · Zbl 1303.68161
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.