Motivated by placement of jobs in physical machines, we introduce and analyze the problem of online recoloring, or online disengagement. In this problem, we are given a set of n weighted vertices and ...a k-coloring of the vertices (vertices represent jobs, and colors represent physical machines). Edges, representing conflicts between jobs, are inserted in an online fashion. After every edge insertion, the algorithm must output a proper k-coloring of the vertices. The cost of recoloring a vertex is the vertex’s weight. Our aim is to minimize the competitive ratio of the algorithm, i.e., the ratio between the cost paid by the online algorithm and the cost paid by an optimal, offline algorithm. We consider a couple of polynomially-solvable coloring variants. Specifically, for 2-coloring bipartite graphs we present an O(logn)-competitive deterministic algorithm and an Ω(logn) lower bound on the competitive ratio of randomized algorithms. For (Δ+1)-coloring, where Δ is the maximal node degree, we present tight bounds of Θ(Δ) and Θ(logΔ) on the competitive ratios of deterministic and randomized algorithms, respectively (where Δ denotes the maximum degree). We also consider the fully dynamic case which allows edge deletions as well as insertions. All our algorithms are applicable to the case where vertices are arbitrarily weighted, and all our lower bounds hold even in the uniform weights (unweighted) case.
A muscle synergies model was suggested to represent a simplifying motor control mechanism by the brainstem and spinal cord. The aim of the study was to investigate the feasibility of such control ...mechanisms in the rehabilitation of post-stroke individuals during the execution of hand-reaching movements in multiple directions, compared to non-stroke individuals.
Twelve non-stroke and 13 post-stroke individuals participated in the study. Muscle synergies were extracted from EMG data that was recorded during hand reaching tasks, using the NMF algorithm. The optimal number of synergies was evaluated in both groups using the Variance Accounted For (VAF) and the Mean Squared Error (MSE). A cross validation procedure was carried out to define a representative set of synergies. The similarity index and the K-means algorithm were applied to validate the existence of such a set of synergies, but also to compare the modulation properties of synergies for different movement directions between groups. The similarity index and hierarchical cluster analysis were also applied to compare between group synergies.
Four synergies were chosen to optimally capture the variances in the EMG data, with mean VAF of 0.917 ± 0.034 and 0.883 ± 0.046 of the data variances, with respective MSE of 0.007 and 0.016, in the control and study groups, respectively. The representative set of synergies was set to be extracted from movement to the center of the reaching space. Two synergies had different muscle activation balance between groups. Seven and 17 clusters partitioned the muscle synergies of the control and study groups. The control group exhibited a gradual change in the activation in the amplitude in the time domain (modulation) of synergies, as reflected by the similarity index, whereas the study group exhibited consistently significant differences between all movement directions and the representative set of synergies. The study findings support the existence of a representative set of synergies, which are modulated to execute movements in different directions.
: Post-stroke individuals differently modulate the activation of synergies to different movement directions than do non-stroke individuals. The conclusion was supported by different muscle activation balances, similarity values and different classifications of synergies among groups.
Direction Modulation of Muscle Synergies in a Hand-Reaching Task Israely, Sharon; Leisman, Gerry; Machluf, Chay ...
IEEE transactions on neural systems and rehabilitation engineering,
2017-Dec., 2017-Dec, 2017-12-00, 20171201, Letnik:
25, Številka:
12
Journal Article
Recenzirano
Functional tasks of the upper extremity can be executed by a variety of muscular patterns, independent of the direction, speed and load of the task. This large number of degrees of freedom imposes a ...significant control burden on the CNS. Previous studies suggested that the human cortex synchronizes a discrete number of neural functional units within the brainstem and spinal cord, i.e. muscle synergies, by linearly combining them to execute a great repertoire of movements. Further exploring this control mechanism, we aim to study whether a single set of muscle synergies might be generalized to express movements in different directions. This was implemented by using a modified version of the non-negative matrix factorization algorithm on EMG data sets of the upper extremity of healthy people. Our twelve participants executed hand-reaching movements in multiple directions. Muscle synergies that were extracted from movements to the center of the reaching space could be generalized to synergies for other movement directions. This finding was also supported by the application of a weighted correlation matrix, the similarity index and the results of the K-means cluster analysis. This might reinforce the notion that the CNS flexibly combines a single set of small number of synergies in different amplitudes to modulate movement for different directions.
Motivated by placement of jobs in physical machines, we introduce and analyze the problem of online recoloring, or online disengagement. In this problem, we are given a set of
n
weighted vertices and ...a
k
-coloring of the vertices (vertices represent jobs, and colors represent physical machines). Edges, representing conflicts between jobs, are inserted in an online fashion. After every edge insertion, the algorithm must output a proper
k
-coloring of the vertices. The cost of recoloring a vertex is the vertex’s weight. Our aim is to minimize the competitive ratio of the algorithm, i.e., the ratio between the cost paid by the online algorithm and the cost paid by an optimal, offline algorithm. We consider a couple of polynomially-solvable coloring variants. Specifically, for 2-coloring bipartite graphs we present an
O
(
log
n
)
-competitive deterministic algorithm and an
Ω
(
log
n
)
lower bound on the competitive ratio of randomized algorithms. For
(
Δ
+
1
)
-coloring, where
Δ
is the maximal node degree, we present tight bounds of
Θ
(
Δ
)
and
Θ
(
log
Δ
)
on the competitive ratios of deterministic and randomized algorithms, respectively (where
Δ
denotes the maximum degree). We also consider the fully dynamic case which allows edge deletions as well as insertions. All our algorithms are applicable to the case where vertices are arbitrarily weighted, and all our lower bounds hold even in the uniform weights (unweighted) case.
PDF
