Det utvidgade abstractet av detta papper framträdde i ESA '99 BHK + schemaläggning beroende jobb på flera maskiner modelleras av grafen multicoloring problem. I detta dokument överväger vi problemet med att minimera den genomsnittliga tiden för slutförande av alla arbetstillfällen. Detta formaliseras som summan multicoloring problem: Med tanke på en graf och antalet färger som krävs av varje vertex, ND en multicoloring som minimerar summan av de största färgerna tilldelas hörnen. Det minskar till den kända summan färgproblem när varje vertex kräver exakt en färg. I detta dokument redovisas en omfattande studie av det sammanlagda flerfärgsproblemet, där tre modeller behandlas: med och utan preferenser, samt samschemaläggning där jobben inte kan börja medan andra körs. Vi etablerar ett linjärt samband mellan approximabiliteten av det maximala oberoende set problemet och approximabiliteten av summan multicoloring problem i alla tre modeller, via en länk till summan färg problemet. Således, för klasser av grafer för vilka den oberoende uppsättningen problem är - ungefärlig, vi få O ( ) - approximationer för förebyggande och co-schemaläggning summan multicoloring, och O ( log n) - approximation för icke förebyggande summan multicoloring. Dessutom ger vi konstant förhållande approximationer för ett antal grundläggande klasser av grafer, inklusive bipartit, linje, begränsad grad, och planar grafer.
Partisumma färgning: Problemet med batch färg så att minimera summan av jobb slutföra tider infördes i REF.
Sum Multicoloring of Graphs
{'venue': 'J. Algorithms', 'journal': 'J. Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}