English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the classical scheduling problem on parallel machines %withprecedence constraints where the precedence graph has the bounded depth $h$.Our goal is to minimize the maximum completion time. We focus on developingapproximation algorithms that use only sublinear space or sublinear time. Wedevelop the first one-pass streaming approximation schemes using sublinearspace when all jobs' processing times differ no more than a constant factor $c$and the number of machines $m$ is at most $\tfrac {2n \epsilon}{3 h c }$. Thisis so far the best approximation we can have in terms of $m$, since nopolynomial time approximation better than $\tfrac{4}{3}$ exists when $m =\tfrac{n}{3}$ unless P=NP. %the problem cannot be approximated within a factorof $\tfrac{4}{3}$ when $m = \tfrac{n}{3}$ even if all jobs have equalprocessing time. The algorithms are then extended to the more general problemwhere the largest $\alpha n$ jobs have no more than $c$ factor difference. %for some constant $0 < \alpha \le 1$. We also develop the first sublinear timealgorithms for both problems. For the more general problem, when $ m \le \tfrac{ \alpha n \epsilon}{20 c^2 \cdot h } $, our algorithm is a randomized$(1+\epsilon)$-approximation scheme that runs in sublinear time. This work notonly provides an algorithmic solution to the studied problem under big data %and cloud computing environment, but also gives a methodological framework fordesigning sublinear approximation algorithms for other scheduling problems.

Sublinear Approximation Schemes for Scheduling Precedence Graphs of Bounded Depth