An exact algorithm with learning for the graph coloring problem

Given an undirected graph G=(V,E), the Graph Coloring Problem (GCP) consists in assigning a color to each vertex of the graph G in such a way that any two adjacent vertices are assigned different colors, and the number of different colors used is minimized. State-of-the-art algorithms generally deal with the explicit constraints in GCP: any two adjacent vertices should be assigned different colors, but do not specially deal with the implicit constraints between non-adjacent vertices implied by the explicit constraints. In this paper, we propose an exact algorithm with learning for GCP which exploits the implicit constraints using propositional logic. Our algorithm is compared with several exact algorithms among the best in the literature. The experimental results show that our algorithm outperforms other algorithms on many instances. Specifically, our algorithm allows to close the open DIMACS instance 4-Fullins_5.     

Variance-penalized Markov decision processes: dynamic programming and reinforcement learning techniques

In control systems theory, the Markov decision process (MDP) is a widely used optimization model involving selection of the optimal action in each state visited by a discrete-event system driven by Markov chains. The classical MDP model is suitable for an agent/decision-maker interested in maximizing expected revenues, but does not account for minimizing variability in the revenues. An MDP model in which the agent can maximize the revenues while simultaneously controlling the variance in the revenues is proposed. This work is rooted in machine learning/neural network concepts, where updating is based on system feedback and step sizes. First, a Bellman equation for the problem is proposed. Thereafter, convergent dynamic programming and reinforcement learning techniques for solving the MDP are provided along with encouraging numerical results on a small MDP and a preventive maintenance problem.     

Stabilization of Rössler chaotic dynamical system using fuzzy logic control algorithm

This paper proposes a fuzzy logic control algorithm (FLCA) to stabilize the Rössler chaotic dynamical system. The fuzzy logic control system is based on a Takagi-Sugeno-Kang inference engine and the stability analysis in the sense of Lyapunov is carried out using Lyapunov’s direct method. The new FLCA is formulated to offer sufficient inequality stability conditions. The asymptotic complexity of our algorithm is analyzed and proved to be lower in comparison with that of linear matrix inequality-based FLCAs. A set of simulation results illustrates the effectiveness of the proposed FLCA.     

Direct measures of digital information processing and communication skills in primary education: Using item response theory for the development and validation of an ICT competence scale

In the past decade, several studies have measured ICT competences from the perspective of ICT self-efficacy. Such indirect measurements tend to have validity problems, as they depend on the pupils' ability to judge their own ICT competences. This study outlines the development of a performance-based digital test and the validation of a direct measure of ICT competence through the use of item response theory (IRT). More specifically, the test and the developed measure focus on primary-school pupils' proficiency in digital information processing and communication. 56 Items were administered to 560 pupils at the end of their primary-school education (age between 10.79 and 13.85 years old). The items were controlled for dimensionality, model-data fit, local item dependence and monotonicity. The final measure contains 27 items that refer to retrieving and processing digital information, and communication with a computer. The results indicate that the instrument is particularly reliable for low and median ability levels. Further refinement and possible future use of the instrument is discussed.     

The role of academic emotions in the relationship between perceived academic control and self-regulated learning in online learning

Self-regulated learning is recognized as a critical factor for successful online learning, and students' perceived academic control and academic emotions are important antecedents of self-regulated learning. Because emotions and cognition are interrelated, investigating the joint relationship between perceived academic control and academic emotions on self-regulated learning would be valuable to understanding the process of self-regulated learning. Therefore, this study examined the role of academic emotions (enjoyment, anxiety, and boredom) in the relationship between perceived academic control and self-regulated learning in online learning. The path model was proposed to test the mediating and moderating effects of academic emotions. Data were collected from 426 Korean college students registered in online courses, and a path analysis was conducted. The results demonstrated that enjoyment mediated the relationship between perceived academic control and self-regulated learning, but the moderating effect of enjoyment was not significant. Boredom and anxiety did not have significant mediating effects on self-regulated learning, whereas they showed significant moderating effects in the relationship between perceived academic control and self-regulated learning. The role of academic emotions in learning and their implications for facilitating students' self-regulated learning in online learning were discussed based on the findings.     

Synthesis and properties of new polyamides based on a hydroxyethyl cinnamide extended from 3,5‐diaminobenzoic acid

A series of new aromatic polyamides containing cinnamide pendent units were prepared from 2′‐(cinnamide)ethyl‐3,5‐diaminobenzoate and various aromatic dicarboxylic acids by the direct polycondensation reaction, with triphenyl phosphite and pyridine as condensing agents. The polyamides were characterized by ¹H NMR, IR, and UV spectroscopy, and gel permeation chromatography. Their thermal stability was studied by thermogravimetric analysis in air, and differential scanning calorimetry. These polymers were readily soluble in polar aprotic solvents and can be cast from their solutions in flexible and tough films. Glass transition temperatures (T_gs) of these polyamides were observed in the range of 225–245°C. Their inherent viscosities varied from 0.77 to 1.12 dL/g that corresponded to weight–average and number–average molecular weights of 39,000–72,700 and 18,800–29,000, respectively. These polymers can be photochemically crosslinked. The photochemical aspects were revealed by means of UV–vis and IR analyses onto thin films. © 2006 Wiley Periodicals, Inc. J Appl Polym Sci 103: 2013–2020, 2007     

Tri-pyramid Robot: Design and kinematic analysis of a 3-DOF translational parallel manipulator

3-DOF translational parallel manipulators have been developed in many different forms, but they still have respective disadvantages in different applications. To overcome their disadvantages, the structure and constraint design of a 3-DOF translational parallel manipulator is presented and named the Tri-pyramid Robot. In the constraint design of the presented manipulator, a conical displacement subset is defined based on displacement group theory. A triangular pyramidal constraint is presented and applied in the constraint designs between the manipulator?s subchains. The structural properties including the decoupled motions, overconstraint elimination, singularity free workspace, fixed actuators and isotropic configuration are analyzed and compared to existing structures. The Tri-pyramid Robot is constrained and realized by a minimal number of 1-DOF joints. The kinematic position solutions, workspace with variation of structural parameters, Jacobian matrix, isotropic and dexterity analysis are performed and evaluated in the numerical simulations.     

Competitive online adaptive scheduling for sets of parallel jobs with fairness and efficiency

We study online adaptive scheduling for multiple sets of parallel jobs, where each set may contain one or more jobs with time-varying parallelism. This two-level scheduling scenario arises naturally when multiple parallel applications are submitted by different users or user groups in large parallel systems, where both user-level fairness and system-wide efficiency are of important concerns. To achieve fairness, we use the well-known equi-partitioning algorithm to distribute the available processors among the active job sets at any time. For efficiency, we apply a feedback-driven adaptive scheduler that periodically adjusts the processor allocations within each set by consciously exploiting the jobs’ execution history. We show that our algorithm achieves asymptotically competitive performance with respect to the set response time, which incorporates two widely used performance metrics, namely, total response time and makespan, as special cases. Both theoretical analysis and simulation results demonstrate that our algorithm improves upon an existing scheduler that provides only fairness but lacks efficiency. Furthermore, we provide a generalized framework for analyzing a family of scheduling algorithms based on feedback-driven policies with provable efficiency. Finally, we consider an extended multi-level hierarchical scheduling model and present a fair and efficient solution that effectively reduces the problem to the two-level model.     

Multi-tier service differentiation by coordinated learning-based resource provisioning and admission control

Multiple Internet applications are often hosted in one datacenter, sharing underlying virtualized server resources. It is important to provide differentiated treatment to co-hosted applications and to improve overall system performance by efficient use of shared resources. Challenges arise due to multi-tier service architecture, virtualized server infrastructure, and highly dynamic and bursty workloads. We propose a coordinated admission control and adaptive resource provisioning approach for multi-tier service differentiation and performance improvement in a shared virtualized platform. We develop new model-independent reinforcement learning based techniques for virtual machine (VM) auto-configuration and session based admission control. Adaptive VM auto-configuration provides proportional service differentiation between co-located applications and improves application response time simultaneously. Admission control improves session throughput of the applications and minimizes resource wastage due to aborted sessions. A shared reward actualizes coordination between the two learning modules. For system agility and scalability, we integrate the reinforcement learning approach with cascade neural networks. We have implemented the integrated approach in a virtualized blade server system hosting RUBiS benchmark applications. Experimental results demonstrate that the new approach meets differentiation targets accurately and achieves performance improvement of applications at the same time. It reacts to dynamic and bursty workloads in an agile and scalable manner.     

Proactive scheduling in distributed computing—A reinforcement learning approach

In distributed computing such as grid computing, online users submit their tasks anytime and anywhere to dynamic resources. Task arrival and execution processes are stochastic. How to adapt to the consequent uncertainties, as well as scheduling overhead and response time, are the main concern in dynamic scheduling. Based on the decision theory, scheduling is formulated as a Markov decision process (MDP). To address this problem, an approach from machine learning is used to learn task arrival and execution patterns online. The proposed algorithm can automatically acquire such knowledge without any aforehand modeling, and proactively allocate tasks on account of the forthcoming tasks and their execution dynamics. Under comparison with four classic algorithms such as Min–Min, Min–Max, Suffrage, and ECT, the proposed algorithm has much less scheduling overhead. The experiments over both synthetic and practical environments reveal that the proposed algorithm outperforms other algorithms in terms of the average response time. The smaller variance of average response time further validates the robustness of our algorithm.