Scheduling in computer and communication systems and generalized graph coloring problems

Abstract

The thesis deals with weighted generalizations of the classical graph coloring problems motivated by scheduling arising in computer and communication systems. The most general problems we attack are called bounded max-vertex/edge-coloring problems and take as input a vertex/edge weighted graph and a bound b. In these problems each color class is of cardinality at most b and of weight equal to that of the heaviest vertex/edge in this class. The objective is to find a proper coloring of the input graph minimizing the sum of all color classes' weights. For unit weights these problems reduce to the known bounded coloring problems, while in the absence of the cardinality bound we get the (unbounded) max-coloring problems. The max-coloring problems have been well motivated and studied in the literature. Max-vertex-coloring problems arise in the management of dedicated memories, organized as buffer pools, which is the case for wireless protocol stacks like GPRS or 3G. Max-edge-coloring problems arise in switch based communication systems like SS/TDMA, where messages are to be transmitted through direct connections established by an underlying network. Moreover, max-coloring problems correspond to scheduling jobs with conflicts in multiprocessor or batch scheduling environments. However, in all practical applications there exist physical constraints on the number of entities (corresponding to vertices/edges of a graph) assigned the same resource (color), which motivate the study of bounded max-coloring problems. In the first part of the thesis we present new complexity and approximation results for several variants of the max-edge-coloring problem with respect to the class of the underlying graph. In particular, we present polynomial algorithms for special graph classes and approximation results for NP-complete variants. For bipartite graphs we present a series of four approximation algorithms; the last of them achieves a 1.74 approximation ratio and improves substantially the known ratio of 2. For trees we give a 3/2-approximation algorithm, two parameterized approximation algorithms and finally a PTAS. We also prove that the problem is NP-complete for complete bi-valued graphs and we present an asymptotic 4/3-approximation algorithm for general bi-valued graphs. In the second part of the thesis we give the first known results for the bounded max-coloring problems. For the bounded max-edge-coloring problem, we prove approximation factors of at most 3 for general and bipartite graphs and 2 for trees. Furthermore, we show that this bounded problem is NP-complete for trees. This is the first complexity result for any max-coloring problem on trees. For the bounded max-vertex-coloring problem we present a generic scheme which becomes a 17/11-approximation algorithm for bipartite graphs, a PTAS for bipartite graphs when b is fixed and also a PTAS for trees even if b is part of the problem's instance

H διατριβή επικεντρώνεται στην αντιμετώπιση ανοικτών ερωτημάτων που αφορούν την πολυπλοκότητα και την προσεγγισιμότητα γενικευμένων προβλημάτων χρωματισμού γράφων, που προκύπτουν ως προβλήματα χρονοπρογραμματισμού σε συστήματα υπολογιστών και επικοινωνιών. Τα γενικότερα από αυτά ονομάζονται προβλήματα φραγμένου μέγιστου χρωματισμού κόμβων/ακμών, όπου δεδομένου ενός γράφου με βάρη στους κόμβους/ακμές και ενός ακεραίου b, αναζητούμε ένα χρωματισμό των κόμβων/ακμών όπου κάθε χρώμα χρησιμοποιείται το πολύ b φορές και το βάρος του ισούται με το βάρος του μεγαλύτερου κόμβου/ακμής που περιέχει. Στόχος είναι η εύρεση ενός χρωματισμού που ελαχιστοποιεί το άθροισμα των βαρών των χρωμάτων. Όταν τα βάρη είναι ίδια, τα προβλήματα είναι γνωστά ως προβλήματα φραγμένου χρωματισμού κόμβων/ακμών, ενώ χωρίς τον περιορισμό στην εμφάνιση των χρωμάτων προκύπτουν τα προβλήματα μέγιστου χρωματισμού κόμβων/ακμών. Τα προβλήματα μέγιστου χρωματισμού έχουν μελετηθεί στη βιβλιογραφία και για καθένα έχουν παρουσιαστεί πρακτικές εφαρμογές. Το πρόβλημα μέγιστου χρωματισμού κόμβων εμφανίζεται σε συστήματα διαχείρισης μνήμης οργανωμένης σε δεξαμενές, όπως συμβαίνει με τη διαχείριση της στοίβας πρωτοκόλλων στα σύγχρονα συστήματα κινητής τηλεφωνίας. Το πρόβλημα μέγιστου χρωματισμού ακμών εμφανίζεται σε συστήματα μεταγωγής μηνυμάτων, όπως στα δορυφορικά συστήματα επικοινωνιών. Στις εφαρμογές αυτές υπάρχουν στην πράξη φυσικοί περιορισμοί στον αριθμό των οντοτήτων που μπορούν να ανατεθούν στον ίδιο φυσικό πόρο, οδηγώντας μας στα προβλήματα φραγμένου μέγιστου χρωματισμού. Στο πρώτο μέρος, παρουσιάζονται αποτελέσματα πολυπλοκότητας και προσεγγισιμότητας του προβλήματος μέγιστου χρωματισμού ακμών. Ειδικότερα, παρουσιάζονται πολυωνυμικοί αλγόριθμοι για ειδικές κλάσεις γράφων και προσεγγιστικοί αλγόριθμοι για γράφους όπου το πρόβλημα είναι ΝΡ-πλήρες. Για διμερείς γράφους δίνεται μία σειρά από τέσσερις προσεγγιστικούς αλγορίθμους, όπου ο τελευταίος βελτιώνει τον λόγο προσέγγισης από 2 σε 1,74. Για δέντρα παρουσιάζεται ένας αλγόριθμος με λόγο προσέγγισης 3/2, δύο παραμετρικοί αλγόριθμοι και ένα προσεγγιστικό σχήμα. Επίσης, αποδεικνύεται ότι το πρόβλημα είναι ΝΡ-πλήρες σε πλήρεις γράφους με δύο βάρη στις ακμές και δίνεται αλγόριθμος με ασυμπτωτικό λόγο προσέγγισης 4/3 για γενικούς γράφους με δύο βάρη. Στο δεύτερο μέρος, παρουσιάζονται τα πρώτα αποτελέσματα για προβλήματα φραγμένου μέγιστου χρωματισμού. Για το πρόβλημα φραγμένου μέγιστου χρωματισμού ακμών, δίνονται αλγόριθμοι με λόγο προσέγγισης 3 για γενικούς γράφους και 2 για δέντρα. Επιπλέον, αποδεικνύεται ότι το πρόβλημα είναι ΝΡ-πλήρες για δέντρα. Για το πρόβλημα φραγμένου μέγιστου χρωματισμού κόμβων παρουσιάζεται ένα γενικευμένο σχήμα, το οποίο οδηγεί σε: λόγο προσέγγισης 17/11 για διμερείς γράφους, προσεγγιστικό σχήμα για διμερείς γράφους αν το b είναι φραγμένο και προσεγγιστικό σχήμα για δέντρα και οποιοδήποτε b