Robust Algorithms for Preemptive Scheduling

Preemptive scheduling problems on parallel machines are classic problems. Given the goal of minimizing the makespan, they are polynomially solvable even for the most general model of unrelated machines. In these problems, a set of jobs is to be assigned to run on a set of m machines. A job can be split into parts arbitrarily and these parts are to be assigned to time slots on the machines without parallelism, that is, for every job, at most one of its parts can be processed at each time. Motivated by sensitivity analysis and online algorithms, we investigate the problem of designing robust algorithms for constructing preemptive schedules. Robust algorithms receive one piece of input at a time. They may change a small portion of the solution as an additional part of the input is revealed. The capacity of change is based on the size of the new piece of input. For scheduling problems, the supremum ratio between the total size of the jobs (or parts of jobs) which may be re-scheduled upon the arrival of a new job j, and the size of j, is called migration factor. We design a strongly optimal algorithm with the migration factor $1-\frac{1}{m}$ for identical machines. Strongly optimal algorithms avoid idle time and create solutions where the (non-increasingly) sorted vector of completion times of the machines is lexicographically minimal. In the case of identical machines this results not only in makespan minimization, but the created solution is also optimal with respect to any ? _p norm (for p>1). We show that an algorithm of a smaller migration factor cannot be optimal with respect to makespan or any other ? _p norm, thus the result is best possible in this sense as well. We further show that neither uniformly related machines nor identical machines with restricted assignment admit an optimal algorithm with a constant migration factor. This lower bound holds both for makespan minimization and for any ? _p norm. Finally, we analyze the case of two machines and show that in this case it is still possible to maintain an optimal schedule with a small migration factor in the cases of two uniformly related machines and two identical machines with restricted assignment.     

Of robot ants and elephants: A computational comparison

In the robotics community, there exist implicit assumptions concerning the computational capabilities of robots. Two computational classes of robots emerge as focal points of recent research: robot ants and robot elephants. Ants have poor memory and communication capabilities, but are able to communicate using pheromones, in effect, turning their work area into a shared memory. By comparison, elephants are computationally stronger, have large memory, and are equipped with strong sensing and communication capabilities. Unfortunately, not much is known about the relation between the capabilities of these models in terms of the tasks they can address. In this paper, we present formal models of both ants and elephants, and investigate if one dominates the other. We present two algorithms: AntEater, which allows elephant robots to execute ant algorithms and ElephantGun, which converts elephant algorithms-specified as Turing machines-into ant algorithms. By exploring the computational capabilities of these algorithms, we reach interesting conclusions regarding the computational power of both models.     

Task Switching After Cerebellar Damage.

The authors of this study investigated task switching following cerebellar damage. The study group consisted of 7 children and adolescents (M age = 13.8 years) who underwent surgical removal of a benign posterior fossa tumor. They were tested at a sufficient interval after surgery (M lag = 6.13 years) for restoration of normal cognitive skills and intelligence. Although all showed normal learning of the task compared with control participants, when rapid behavioral changes were required (short preparation time), they exhibited behavioral rigidity manifested by enhanced switching cost. These results are in line with another study on serial reaction time with the same patients (A. Berger et al., in press). They have important implications for our understanding of the cognitive sequelae of early cerebellar damage as well as the involvement of the cerebellum in task switching. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

Approximation Algorithms for Quickest Spanning Tree Problems

Let $G=(V,E)$ be an undirected multigraph with a special vertex ${\it root} \in V$, and where each edge $e \in E$ is endowed with a length $l(e) \geq 0$ and a capacity $c(e) > 0$. For a path $P$ that connects $u$ and $v$, the {\it transmission time} of $P$ is defined as $t(P)=\mbox{\large$\Sigma$}_{e \in P} l(e) + \max_{e \in P}\!{(1 / c(e))}$. For a spanning tree $T$, let $P_{u,v}^T$ be the unique $u$--$v$ path in $T$. The {\sc quickest radius spanning tree problem} is to find a spanning tree $T$ of $G$ such that $\max _{v \in V} t(P^T_{root,v})$ is minimized. In this paper we present a 2-approximation algorithm for this problem, and show that unless $P =NP$, there is no approximation algorithm with a performance guarantee of $2 - \epsilon$ for any $\epsilon >0$. The {\sc quickest diameter spanning tree problem} is to find a spanning tree $T$ of $G$ such that $\max_{u,v \in V} t(P^T_{u,v})$ is minimized. We present a ${3 \over 2}$-approximation to this problem, and prove that unless $P=NP$ there is no approximation algorithm with a performance guarantee of ${3 \over 2}-\epsilon$ for any $\epsilon >0$.     

C-Reactive Protein Velocity (CRPv) as a New Biomarker for the Early Detection of Acute Infection/Inflammation

C-reactive protein (CRP) is considered a biomarker of infection/inflammation. It is a commonly used tool for early detection of infection in the emergency room or as a point-of-care test and especially for differentiating between bacterial and viral infections, affecting decisions of admission and initiation of antibiotic treatments. As C-reactive protein is part of a dynamic and continuous inflammatory process, a single CRP measurement, especially at low concentrations, may erroneously lead to a wrong classification of an infection as viral over bacterial and delay appropriate antibiotic treatment. In the present review, we introduce the concept of C-reactive protein dynamics, measuring the velocity of C-reactive protein elevation, as a tool to increase this biomarker’s diagnostic ability. We review the studies that helped define new metrics such as estimated C-reactive protein velocity (velocity of C-reactive protein elevation from symptoms’ onset to first C-reactive protein measurement) and the measured C-reactive protein velocity (velocity between sequential C-reactive protein measurements) and the use of these metrics in different clinical scenarios. We also discuss future research directions for this novel metric.