<abstract xmlns="http://www.w3.org/1999/xhtml">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 <italic>v</italic>1, . . . , <italic>vn</italic> and it must decide about <italic>vi</italic> by only looking at the subhypergraph <italic>Hi</italic> = (<italic>Vi</italic>, <italic>Ei</italic>) where <italic>Vi</italic> = {<italic>v</italic>1, . . . , <italic>vi</italic>} and E<italic>i</italic> contains the edges of the hypergraph which are subsets of <italic>Vi</italic>. 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.</abstract>

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 v1, . . . , vn and it must decide about vi by only looking at the subhypergraph Hi = (Vi, Ei) where Vi = {v1, . . . , vi} and Ei contains the edges of the hypergraph which are subsets of Vi. 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.

Online hypergraph coloring with rejection

University of Szeged, Institute of Informatics

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Online hypergraph coloring with rejection"}

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...

Online hypergraph coloring with rejection

Publié en ligne: 08 juin 2015

Pages: 5 - 17

Reçu: 11 août 2014

DOI: https://doi.org/10.1515/ausi-2015-0009

© Csanád Imreh et al.

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.