TY - JOUR

T1 - Resource-sharing systems and hypergraph colorings

AU - Lin, Wu-Hsiung

AU - Chang, Gerard J.

PY - 2011/11/1

Y1 - 2011/11/1

N2 - A resource-sharing system is modeled by a hypergraph H in which a vertex represents a process and an edge represents a resource consisting of all vertices (processes) that have access to it. A schedule of H=(V,E) is a mapping f:ℕ→2 V, where f(i) is an independent set of H which consists of processes that operate at round i. The rate of f is defined as rate (f)=lim sup n→∞∑ n i=1|f(i)|/(n|V|) , which is the average fraction of operating processes at each round. The purpose of this paper is to study optimal rates for various classes of schedules under different fairness conditions. In particular, we give relations between these optimal rates and fractional/circular chromatic numbers. For the special case of the hypergraph is a connected graph, a new derivation for the previous result by Yeh and Zhu is also given.

AB - A resource-sharing system is modeled by a hypergraph H in which a vertex represents a process and an edge represents a resource consisting of all vertices (processes) that have access to it. A schedule of H=(V,E) is a mapping f:ℕ→2 V, where f(i) is an independent set of H which consists of processes that operate at round i. The rate of f is defined as rate (f)=lim sup n→∞∑ n i=1|f(i)|/(n|V|) , which is the average fraction of operating processes at each round. The purpose of this paper is to study optimal rates for various classes of schedules under different fairness conditions. In particular, we give relations between these optimal rates and fractional/circular chromatic numbers. For the special case of the hypergraph is a connected graph, a new derivation for the previous result by Yeh and Zhu is also given.

KW - Circular chromatic number

KW - Fractional chromatic number

KW - Hypergraph

KW - Resource-sharing system

UR - http://www.scopus.com/inward/record.url?scp=83555172694&partnerID=8YFLogxK

U2 - 10.1007/s10878-010-9295-9

DO - 10.1007/s10878-010-9295-9

M3 - Article

AN - SCOPUS:83555172694

VL - 22

SP - 499

EP - 508

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 4

ER -