NP-completness

Scheduling tasks on heterogeneous resources distributed over a grid computing system is an NPcomplete problem. The main aim for several researchers is to develop variant scheduling algorithms for achieving optimality, and they have shown a good performance for tasks scheduling regarding resources selection. However, using of the full power of resources is still a challenge. In this paper, a new heuristic algorithm called Sort-Mid is proposed. It aims to maximizing the utilization and minimizing the makespan. The new strategy of Sort-Mid algorithm is to find appropriate resources.

7p trinhthamhodang1 16-11-2019 23 1   Download

Chương 3 trang bị cho người học những kiến thức cơ bản về lập trình song song. Nội dung chính trong chương này gồm có: Cơ bản về giao tiếp bằng phương pháp trao đổi thông điệp (message passing), thư viện giao diện trao đổi thông điệp (Message Passing Interface – MPI), máy ảo song song (Parallel Virtual Machine-PVM), thiết kế và xây dựng một chương trình (giải một bài toán (NPcomplete) sử dụng MPI và C.

58p whocare_d 22-09-2016 57 9   Download

We show how global constraints such as transitivity can be treated intensionally in a Zero-One Integer Linear Programming (ILP) framework which is geared to find the optimal and coherent partition of coreference sets given a number of candidate pairs and their weights delivered by a pairwise classifier (used as reliable clustering seed pairs). In order to find out whether ILP optimization, which is NPcomplete, actually is the best we can do, we compared the first consistent solution generated by our adaptation of an efficient Zero-One algorithm with the optimal solution. ...

9p bunthai_1 06-05-2013 42 1   Download

The lexicalist approach to Machine Translation offers significant advantages in the development of linguistic descriptions. However, the Shake-and-Bake generation algorithm of (Whitelock, 1992) is NPcomplete. We present a polynomial time algorithm for lexicalist MT generation provided that sufficient information can be transferred to ensure more determinism.

7p bunmoc_1 20-04-2013 40 1   Download

và người bán đấu giá phải giải quyết một vấn đề tối ưu hóa NP-đầy đủ để xác định phân vùng tối ưu. Thuật toán giải pháp nhanh chóng không (thời gian đa thức) có sẵn cho các vấn đề NPcomplete, vấn đề xác định người chiến thắng 'có thể không thực tế khó giải quyết.

103p banhbeo3 07-11-2011 62 5   Download

Many problems of practical significance are NPcomplete but are too important to abandon merely because obtaining an optimal solution is intractable (khó). If a problem is NP-complete, we are unlikely to find a polynomial time algorithm for solving it exactly, but it may still be possible to find near-optimal solution in polynomial time.

22p lucky156 04-06-2010 209 18   Download