排序方式: 共有5条查询结果,搜索用时 0 毫秒
1
1.
Scheduling Independent Multiprocessor Tasks 总被引:1,自引:0,他引:1
We study the problem of scheduling a set of n independent multiprocessor tasks with prespecified processor allocations on a fixed number of processors. We propose a linear time algorithm that finds a schedule of minimum makespan in the preemptive model, and a linear time approximation algorithm that finds a schedule of makespan within a factor of (1+\eps) of optimal in the non-preemptive model. We extend our results by obtaining a polynomial time approximation scheme for the parallel processors variant of the multiprocessor task model. 相似文献
2.
Abstract. We study the problem of scheduling a set of n independent multiprocessor tasks with prespecified processor allocations on a fixed number of processors. We propose a linear
time algorithm that finds a schedule of minimum makespan in the preemptive model, and a linear time approximation algorithm
that finds a schedule of makespan within a factor of (1+\eps) of optimal in the non-preemptive model. We extend our results by obtaining a polynomial time approximation scheme for the
parallel processors variant of the multiprocessor task model. 相似文献
3.
A. Abouelaoualim K.Ch. Das L. Faria Y. Manoussakis C. Martinhon R. Saad 《Theoretical computer science》2008
This paper deals with the existence and search for properly edge-colored paths/trails between two, not necessarily distinct, vertices s and t in an edge-colored graph from an algorithmic perspective. First we show that several versions of the s−t path/trail problem have polynomial solutions including the shortest path/trail case. We give polynomial algorithms for finding a longest properly edge-colored path/trail between s and t for a particular class of graphs and characterize edge-colored graphs without properly edge-colored closed trails. Next, we prove that deciding whether there exist k pairwise vertex/edge disjoint properly edge-colored s−t paths/trails in a c-edge-colored graph Gc is NP-complete even for k=2 and c=Ω(n2), where n denotes the number of vertices in Gc. Moreover, we prove that these problems remain NP-complete for c-edge-colored graphs containing no properly edge-colored cycles and c=Ω(n). We obtain some approximation results for those maximization problems together with polynomial results for some particular classes of edge-colored graphs. 相似文献
4.
MN Manoussakis KG Kistis X Liu V Aidinis A Guialis HM Moutsopoulos 《Canadian Metallurgical Quarterly》1993,32(6):449-455
Counterimmunoelectrophoresis (CIE), RNA precipitation, ELISA and immunoblotting against cytoplasmic HeLa cell extract (IB-HeLa) and erythrocyte extract (IB-RBC) were applied to detect anti-Ro(SSA) antibodies in 93 sera selected from patients with various autoimmune diseases [47 were anti-Ro(SSA) positive by CIE]. The RNA precipitation assay, which demonstrated the highest sensitivity was selected as the reference method. CIE was found to be reliable with a specificity of 100% and a sensitivity of 89%. ELISA showed a comparable specificity (95%) but somewhat lower sensitivity (72%). Antibodies to 52 or 60 kDa Ro(SSA) proteins by IB-HeLa demonstrated a high specificity (95 and 97% respectively) but a low overall sensitivity (36 and 17% respectively). Anti-Ro(SSA) antibodies to 52, 54 and 60 kDa erythrocyte proteins by IB-RBC, had a variable overall specificity (95, 97 and 57%) and sensitivity (51, 13 and 34%). The anti-52 kDa antibodies detected by IB-HeLa correlated to those found by IB-RBC (P < 0.001) and occurred predominantly in primary Sj?gren's syndrome (P < 0.001, sensitivity: 71 and 77%) as well as in sera with anti-Ro(SSA) and anti-La(SSB) antibodies (P < 0.001). These findings confirm that RNA precipitation assay has the highest sensitivity and specificity for anti-Ro(SSA) antibody detection. However, until a more sensitive ELISA is available, CIE because of its reliability appears to be the method of choice. Finally IB-RBC was found to be more sensitive than IB-HeLa for the detection of anti-Ro52 kDa antibodies. 相似文献
5.
We give anO(log4
n)-timeO(n
2)-processor CRCW PRAM algorithm to find a hamiltonian cycle in a strong semicomplete bipartite digraph,B, provided that a factor ofB (i.e., a collection of vertex disjoint cycles covering the vertex set ofB) is computed in a preprocessing step. The factor is found (if it exists) using a bipartite matching algorithm, hence placing
the whole algorithm in the class Random-NC.
We show that any parallel algorithm which can check the existence of a hamiltonian cycle in a strong semicomplete bipartite
digraph in timeO(r(n)) usingp(n) processors can be used to check the existence of a perfect matching in a bipartite graph in timeO(r(n)+n
2
/p(n)) usingp(n) processors. Hence, our problem belongs to the class NC if and only if perfect matching in bipartite graphs belongs to NC.
We also consider the problem of finding a hamiltonian path in a semicomplete bipartite digraph. 相似文献
1