{'fraction_non_alphanumeric': 0.02081165452653486, 'fraction_numerical': 0.0, 'mean_word_length': 4.83030303030303, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
APPROXIMATING A PARALLEL TASK SCHEDULE USING LONGEST PATH

This paper focuses on an NP-hard parallel task-scheduling problem. The problem receives input in the form of a precedence graph representation of a job where the objective is a taskto-processor allocation that minimizes the total computation time of the job. The sub-tasks can be executed in parallel on a network of identical computing entities. Communication and latency constraints are also imposed making the problem more difficult to solve. Presented is an approximation algorithm for this problem that runs in O(mn) time, where n is the number of nodes (or tasks) in the job and m is the number of edges. The algorithm utilizes the fact that the longest path problem can be solved to optimality, in O(m) steps, on graphs containing no directed cycles which is consistent with precedence graphs. Presented are results of the performance of the algorithm through extensive testing on random graphs.