Article
Polynomial-time approximation algorithms for the coloring problem in some cases
We consider the coloring problem for hereditary graph classes, i.e. classes of simple unlabeled graphs closed under deletion of vertices. For the family of the hereditary classes of graphs defined by forbidden induced subgraphs with at most four vertices, there are three classes with an open complexity of the problem. For the problem and the open three cases, we present approximation polynomial-time algorithms with performance guarantees.
This proceedings publication is a compilation of selected contributions from the “Third International Conference on the Dynamics of Information Systems” which took place at the University of Florida, Gainesville, February 16–18, 2011. The purpose of this conference was to bring together scientists and engineers from industry, government, and academia in order to exchange new discoveries and results in a broad range of topics relevant to the theory and practice of dynamics of information systems. Dynamics of Information Systems: Mathematical Foundation presents state-of-the art research and is intended for graduate students and researchers interested in some of the most recent discoveries in information theory and dynamical systems. Scientists in other disciplines may also benefit from the applications of new developments to their own area of study.
In this paper, we consider the minimizing total weighted completion time in preemptive equal-length job with release dates scheduling problem on a single machine. This problem is known to be open. Here, we give some properties of optimal schedules for the problem and its special cases.
Consideration was given to a graphic realization of the method of dynamic programming. Its concept was demonstrated by the examples of the partition and knapsack problems. The proposed method was compared with the existing algorithms to solve these problems.
We study the scheduling problem for single machine with preemptions of jobs. On a machine it is necessary to process a set of n jobs. Simultaneous processing is prohibited, but interrupts in processing jobs is possible. Each job j of the set is characterize by it's weight w_j, release date r_j = j - 1 and processing time p_j = 2. The only restriction is that weights w_j are non-decreasing. The objective function can be expressed as the sum of weighted completion times. We suggest the polynomial algorithm with complexity O(n^4) operations which gives us the Pareto-optimal schedules for each set of jobs. In the algorithm we use generalized Smith's rule, to obtain particular schedules after moment r_n and to prove some important lemmas for reduction of search of suitable schedules.
A form for an unbiased estimate of the coefficient of determination of a linear regression model is obtained. It is calculated by using a sample from a multivariate normal distribution. This estimate is proposed as an alternative criterion for a choice of regression factors.