Minimizing Makespan in Sublinear Time via Weighted Random Sampling Bin Fu, Yumei Huo, Hairong Zhao Abstract We consider the classical makespan minimization scheduling problem where n n jobs must be scheduled on m m identical machines. Using weighted random sampling, we developed two sublinear time approximation schemes: one for the case where n n is known and the other for the case where n n is unknown. Both algorithms not only give a ( 1 + 3 ​ ϵ ) (1+3\epsilon) -approximation to the optimal makespan but also generate a sketch schedule. Our first algorithm, which targets the case where n n is known and draws samples in a single round under weighted random sampling, has a running time of O ~ ​ ( m 5 ϵ 4 ​ n + A ⁡ ( ⌈ m ϵ ⌉ , ϵ ) ) \tilde{O}(\tfrac{m^{5}}{\epsilon^{4}}\sqrt{n}+A(\left\lceil m\over\epsilon\right\rceil,{\epsilon})) , where A ⁡ ( 𝒩 , α ) A(\mathcal{N},\alpha) is the time complexity of any ( 1 + α ) (1+\alpha) -approximation scheme for the makespan minimization of 𝒩 \mathcal{N} jobs. The second algorithm addresses the case where n n is unknown. It uses adaptive weighted random sampling, and runs in sublinear time O ~ ​ ( m 5 ϵ 4 ​ n + A ⁡ ( ⌈ m ϵ ⌉ , ϵ ) ) \tilde{O}\left(\tfrac{m^{5}}{\epsilon^{4}}\sqrt{n}+A(\left\lceil m\over\epsilon\right\rceil,{\epsilon})\right) . We also provide an implementation that generates a weighted random sample using O ⁡ ( log ⁡ n ) O(\log n) uniform random samples. 1 Introduction We study the classical makespan minimization scheduling problem on parallel machines, where there are n jobs to be scheduled on m identical parallel machines. The jobs are all available for processing at time 0 and are labeled 1,2,\dots,n . Each job j , 1\leq j\leq n , has a processing time p_{j} and can be scheduled on any machine. At any time, only one job can be scheduled on each machine. A job cannot be interrupted once it is started. Given a schedule S , let C_{j} be the completion time of job j in S , the makespan of the schedule S is C_{max}=\max_{1\leq j\leq n}C_{j} . The objective is to find the minimum makespan among all schedules, denoted as OPT(I) , or simply OPT if I is clear from the context. This classical scheduling problem, also known as the load balancing problem, has many applications in the manufacturing and service industries. Additionally, it plays significant roles in computer science, including applications in client-server networks, database systems, and cloud computing. In this paper, our goal is to design sublinear time approximation algorithms for this classical scheduling problem. Sublinear time algorithms are suited for situations where the input data is so large that even a single scan of the entire input cannot be afforded, so the solution is expected to be given by reading only a minuscule fraction of the input data and using only sublinear time. As Czumaj and Sohler noted in their survey paper [ 10 ] , sublinear time algorithms have their roots in the study of massive data sets, where even linear-time algorithms can be prohibitively slow. Hence, there is a need to develop algorithms whose running times are not only polynomial, but actually are sublinear in the input size. Such algorithms do not need to read the entire input; instead, they determine the output by inspecting only a subset of input elements. Sublinear time algorithms are typically randomized and return only an approximate solution rather than the exact one. Developing sublinear time algorithms not only speeds up computation, but also reveals some interesting properties of computation, especially the power of randomization. So far, most sublinear time algorithms have been developed based on uniform random sampling. While uniform sampling is easy to implement, it has a drawback in scheduling problems: When the jobs’ processing times vary significantly, failing to sample the largest processing time may result in a significant loss of accuracy. Consider two instances of job inputs: in the first input, all job processing times are a small number \epsilon , while in the second input, all jobs’ processing times are \epsilon except for one job, which has a very large processing time X . No sampling scheme can distinguish between these two inputs until it samples the job with processing time X , and with uniform sampling, it would require a linear number of samples to hit X . Therefore, in this paper, we develop sublinear time algorithms using weighted random sampling. We formally define weighted random sampling as follows. Definition 1 Given n elements, where each element j is associated with a weight w_{j} , and the total weight is denoted by W=\sum_{j=1}^{n}w_{j} , Weighted Random Sampling (WRS) is a technique in which the probability of selecting an element is proportional to its weight, i.e., \tfrac{w_{j}}{W} . 1.1 Related work The makespan minimization problem has been known to be NP-hard for a long time. In the 1960s, Graham showed that the List Scheduling rule and the Longest Processing Time First rule give approximations of 2-\tfrac{1}{m} and \tfrac{4}{3}-\tfrac{1}{3m} , respectively (see [ 17 ] and [ 18 ] ). Later, many approximation schemes have been developed for both the case where the number of machines m is fixed ( [ 21 ] ) and the case where m is arbitrary ( [ 20 , 23 , 22 ] ). Over the past few decades, sublinear time algorithms have been developed for various applications, such as algebra, graph theory, geometry, string and set operations, optimization, and probability theory. Some examples are checking polygon intersections [ 6 ] , approximating the average degree in a graph [ 11 , 14 ] , estimating the cost of a minimum spanning tree [ 7 , 9 , 8 ] , finding geometric separators [ 12 ] , property testing [ 15 , 16 ] , and recently graph problems such as [ 4 , 3 , 2 ] . All of these sublinear time algorithms are based on uniform random sampling. So far, only a few works on sublinear time algorithms have utilized the weighted sampling method. For example, Motwani, Panigrahy, and Xu [ 25 ] and Lorenzo and T \check{e} tek [ 5 ] applied it for estimating the sum, while Batu, Berenbrink, and Sohle [ 1 ] used it for bin packing. For the scheduling problem, to the best of our knowledge, the only works on sublinear time algorithms are those in [ 13 ] and [ fhz25sublinear ] for the classical scheduling problems under uniform random sampling setting. In [ 13 ] , sublinear time algorithms are developed for the parallel machine makespan minimization scheduling problem with chain precedence constraints and in [ fhz25sublinear ] the sublinear time algorithms are presented for the classical parallel machine makespan minimization problem with constrained processing times, and the algorithm is then extended to the problem with precedence constraints where the precedence graph has limited depth. 1.2 New contribution In this paper, we develop sublinear time algorithms for the makespan minimization problem using weighted random sampling where the weight of a job is simply its processing time. Note that the lower bound of \Omega(\sqrt{n}) [ 25 ] for computing an approximate sum of n positive numbers using weighted random sampling also applies to our problem. Our sublinear algorithms start with a key step, which is to derive a sketch of the input instance by drawing \tilde{O}(\sqrt{n}) samples. When the number of jobs n is given, we draw the samples in a single round. With high probability, the samples will include all jobs with large processing time and some medium jobs, but no small jobs. To construct the sketch of the input, we include all the sampled large jobs, divide the medium jobs into groups, where the number of jobs in each group is estimated using a generalized birthday paradox argument based on the samples from the group, and disregard the small jobs. When the number of jobs n is unknown, we employ adaptive sampling to estimate the number of jobs. Specifically, we sample jobs in several rounds, increase the number of samples geometrically until we can apply the birthday paradox argument to estimate the number of jobs in all groups. The second step of our algorithms is to compute an approximation of the optimal makespan for the scheduling problem based on the sketch constructed from the first step. To this end, we may employ any existing approximation scheme for makespan minimization as a black-box procedure and apply it to the large jobs. For example, we can apply approximation schemes proposed in [ 19 , 24 , 23 ] and the most recent one developed by Jansen, Klein, and Verschae [ 22 ] that returns a (1+\alpha) -approximation for the instance of \mathcal{N} jobs in 2^{O({1\over\alpha}(\log{1\over\alpha})^{4})}+O(\mathcal{N}\log\mathcal{N}) time. In many applications, one needs not only an approximate value of the optimal makespan, but also a schedule that specifies how the jobs are assigned to machines. To meet this requirement, we use the concept of “sketch schedule” and show that we can modify our algorithms to compute “sketch schedule” while keeping the running time still sublinear in the number of jobs. Moreover, we present how “sketch schedule” can be used to construct a concrete schedule for jobs in I when full job information is available. Let A(\mathcal{N},\alpha) be the time complexity of any (1+\alpha) -approximation scheme for \mathcal{N} jobs. Our main results can be summarized in the following two theorems. Theorem 1 When the number of jobs n is known, using non-adaptive weighted sampling, there is a randomized (1+\epsilon) -approximation algorithm for the makespan minimization problem that runs in \tilde{O}(\tfrac{m^{5}}{\epsilon^{4}}\sqrt{n}+A(\left\lceil m\over\epsilon\right\rceil,{\epsilon})) time. Furthermore, it can compute a sketch schedule \tilde{S} , represented using O(\tfrac{m^{2}}{\epsilon^{2}}\ln(mn^{2})) space, which can be used to generate a schedule of the jobs subsequently with a makespan of at most (1+3\epsilon) times the optimal. Theorem 2 When the number of jobs is unknown, there is a randomized (1+\epsilon) -approximation algorithm for the makespan scheduling problem that uses adaptive weighted random samplings, runs in \tilde{O}\left(\tfrac{m^{5}}{\epsilon^{4}}\sqrt{n}+A(\left\lceil m\over\epsilon\right\rceil,{\epsilon})\right) time. Furthermore, it can compute a sketch schedule, represented using O(\tfrac{m^{2}}{\epsilon^{2}}(\log{\tfrac{nm}{\epsilon}))} space, which can be used later to generate a schedule with a makespan at most (1+3\epsilon) times the optimal. The paper is organized as follows. In Section 2 , we introduce some key definitions and present the structure of our sublinear time algorithms where two main steps are deriving the sketch of the input and computing the approximate value of the optimal makespan, respectively. In this section, we provide an analysis of the algorithm in general, and then specifically in Section 2.3 we derive the sublinear time approximation schemes to compute the approximate value of the optimal makespan assuming the sketch of the input has been derived, for which the detailed sampling algorithms are designed and analyzed in Section 3 by differentiating the cases where the number of jobs, n , is known in the subsections 3.2 and unknown in subsection , respectively. Then in Section 4 , we discuss some issues related to our sublinear time algorithms, including how to perform weighted random sampling using uniform random sampling in subsection 4.1 and applying the idea of job sketch to deterministic approximation algorithm design for our scheduling problems in subsection 4.2 . Finally, we draw the concluding remarks in Section 5 . 2 Definitions and the Framework of Our sublinear Time Algorithms 2.1 Definitions Given an instance of the problem I=\{p_{j},1\leq j\leq n\} , our algorithms draw a sublinear size of samples, then estimate the original job set based on the samples, and finally compute the approximate value of the optimal makespan based on the estimated job set. To estimate instance I , we construct a “sketch” instance \tilde{I} , which can be stored in a space of size sublinear in n . Let p_{max} be the largest job processing time in the input. Since p_{max} is unknown, our algorithm will first obtain an upper bound of p_{max} , denoted as p_{max}^{\prime} . For a parameter \delta , 0<\delta<1 , which will be decided later, we partition the jobs into groups such that group k contains all the jobs with the processing times in the interval I_{k}=(p_{max}^{\prime}(1-\delta)^{k},p_{max}^{\prime}(1-\delta)^{k-1}] , k\geq 1 . For convenience, we also use j\in I_{k} interchangeably with p_{j}\in I_{k} . A “sketch” instance \tilde{I} is formally defined as follows. Definition 2 Given an instance of the problem I=\{p_{j},1\leq j\leq n\} and p_{max}^{\prime} such that p_{max}\leq p_{max}^{\prime} , let n_{k} be the number of jobs j\in I_{k} where I_{k}=(p_{max}^{\prime}(1-\delta)^{k},p_{max}^{\prime}(1-\delta)^{k-1}] , k\geq 1 . An input sketch of I is denoted as \tilde{I}=\{\langle\tilde{n}_{k},\tilde{p}_{k}\rangle\} , where \langle\tilde{n}_{k},\tilde{p}_{k}\rangle provides an estimate of jobs of I from the interval I_{k} : \tilde{n}_{k} is an estimate of the numbers of the jobs, n_{k} , and \tilde{p}_{k}=p_{max}^{\prime}(1-\delta)^{k-1} is the estimated processing time for these jobs. Next, we define an (\alpha,\beta_{1},\beta_{2}) -sketch of I , which characterize how well a sketch approximates I in terms of the number of jobs in each interval, and OPT(I) . Without loss of generality, the sketch only contains those intervals I_{k} for which \tilde{n}_{k}>0 . Definition 3 Given an instance of the problem I we say an input sketch \tilde{I}=\{\langle\tilde{n}_{k},\tilde{p}_{k}\rangle:1\leq k\leq t\} is an (\alpha,\beta_{1},\beta_{2}) -sketch of I if the following conditions hold: i. For every k\in[1,t] with \tilde{n}_{k}>0 , (1-\alpha)\,n_{k}\leq\tilde{n}_{k}\leq(1+\alpha)\,n_{k} ii. (1-\beta_{1})\,OPT(I)\leq OPT(\tilde{I})\leq(1+\beta_{1})\,OPT(I). iii. The total processing time of the jobs from intervals I_{k} not included in the sketch, i.e., those with \tilde{n}_{k}=0 or the intervals I_{k},k>t , is at most \beta_{2}\cdot OPT(I) . 2.2 The Framework of the Sublinear Time Algorithms Our sublinear time algorithms follow the same structure, which consists of two stages: compute a sketch and derive an approximation from the sketch instance. Formally, the main structure is presented as follows. Main Algorithm: Input: \epsilon , m , I=\{p_{j}:1\leq j\leq n\} Output: an approximate value of OPT(I) i. generate an (\alpha,\beta_{1},\beta_{2}) -sketch instance for the original instance I , \tilde{I}=\{\langle\tilde{n}_{k},\tilde{p}_{k}\rangle,1\leq k\leq t\} , where \alpha , \beta_{1} and \beta_{2} all depend on \epsilon ii. compute an approximate value of OPT(I) based on \tilde{I} . If there exist efficient algorithms \mathcal{A}_{1} and \mathcal{A}_{2} for computing a sketch instance and an approximation for the sketch instance, respectively, we can simply apply \mathcal{A}_{1} in the first step and \mathcal{A}_{2} in the second step, and thus obtain an approximation for the problem, as presented in the following proposition. Proposition 1 Assuming that (1) there exists an algorithm \mathcal{A}_{1}(.) that computes an (\alpha,\beta_{1},\beta_{2}) -sketch for any given instance I of n jobs in time T_{1}(\alpha,\beta_{1},\beta_{2},n,m) , and (2) there exists another algorithm \mathcal{A}_{2}(.) that computes a (1+\gamma) -approximation for a sketch instance \tilde{I}=\{\langle\tilde{n}_{k},\tilde{p}_{k}\rangle:1\leq k\leq t\} , \tilde{n}=\sum_{k=1}^{t}\tilde{n}_{k} , in T_{2}(\gamma,t,\tilde{n},m) time. Then there exists an approximation algorithm for any instance I that returns a value X , such that (1-\beta_{1})OPT(I)\leq X\leq(1+\gamma)(1+\beta_{1})OPT(I) with running time O(T_{1}(\alpha,\beta_{1},\beta_{2},n,m)+T_{2}(\gamma,t,(1+\alpha)n,m)) . So far in the literature, there is no existing algorithm to obtain an input sketch \tilde{I}=\{\langle\tilde{n}_{k},\tilde{p}_{k}\rangle\} , and more specifically an (\alpha,\beta_{1},\beta_{2}) -sketch of I in sublinear time. Therefore, one of the main tasks in this paper is to develop sublinear time algorithms for obtaining an (\alpha,\beta_{1},\beta_{2}) -sketch for any instance I . The details of these algorithms will be presented in Section 3 . As for the second step, although there is no existing sublinear time algorithm for computing an approximation from the input sketch, we may employ the existing approximation schemes that have been developed for the classical makespan minimization scheduling problem and develop sublinear time algorithms for the input sketch. We present the details in the following subsection. 2.3 Sublinear Time Approximation Schemes for a Sketch Instance Let A be any approximation scheme for the classical parallel machine makespan minimization scheduling problem, such as the ones proposed in [ 19 , 24 , 23 ] and the most recent one developed by Jansen, Klein, and Verschae [ 22 ] . We design an efficient meta-algorithm that uses A as a black box to obtain (1+\epsilon) -approximation for a sketch instance. The main idea is to apply the black box approximation scheme to the largest jobs and use a batch processing method to assign the remaining jobs. Meta-Algorithm: Input: \epsilon , m \tilde{I}=\{\langle\tilde{n}_{k},\tilde{p}_{k}\rangle:1\leq k\leq t\} , \tilde{p}_{k}>\tilde{p}_{k+1} for kP/m . But this is impossible, since the total processing time is P . (2) P/m\geq T_{0} . In this case, T=(1+\delta)P/m . Then the interval between T and P/m has length T-P/m=\delta P/m\geq\delta T_{0}\geq\tilde{p}_{k_{0}} . In other words, every remaining job can fit in the interval between P/m and T . If at some point a job cannot be scheduled with the completion time at or before T , we get a contradiction as in the first case. The above Meta-algorithm returns only an approximation of the optimal makespan, without providing insight into how to construct a schedule with that makespan. However, in many applications, one needs not only an approximate value of the optimal makespan, but also a schedule that specifies how the jobs are assigned to machines. In the following, we first introduce the concept of “sketch schedule” and show we can modify the Meta-algorithm to compute a “sketch schedule” while still keeping the overall running time sublinear. Then, we present how a “sketch schedule” can be used to construct a concrete schedule for jobs in I when full job information is available. 2.4 Sketch Schedule Definition 4 Given a sketch instance \tilde{I}=\{\langle\tilde{n}_{k},\tilde{p}_{k}\rangle,1\leq k\leq t\} for instance I , we denote a sketch schedule for I as \tilde{S}=\{\langle\tilde{n}_{i,j},\tilde{p}_{j}\rangle,1\leq i\leq m,1\leq j\leq t,\sum_{i}\tilde{n}_{i,j}=\tilde{n}_{j}\} , where \langle\tilde{n}_{i,j},\tilde{p}_{j}\rangle represents that \tilde{n}_{i,j} jobs with processing time \tilde{p}_{j} are assigned to machine M_{i} . Now we show that we can modify the Meta-algorithm to generate a sketch schedule. Modified Meta-Algorithm: Input: \epsilon , m \tilde{I}=\{\langle\tilde{n}_{k},\tilde{p}_{k}\rangle:1\leq k\leq t\} , \tilde{p}_{k}>\tilde{p}_{k+1} for k0 vi. Compute the assignment of these jobs as follows: (a) i=1 (b) While k_{0}\leq t i. Compute the number of jobs from \langle\tilde{n}^{\prime}_{k_{0}},\tilde{p}_{k_{0}}\rangle that can be scheduled on M_{i} by time T , that is, \tilde{n}^{\prime\prime}_{k_{0}}=\min\{\tilde{n}^{\prime}_{k_{0}},\left\lfloor\tfrac{T-T_{i}}{\tilde{p}_{k_{0}}}\right\rfloor\} ii. Update T_{i}=T_{i}+\tilde{n}^{\prime\prime}_{k_{0}}\tilde{p}_{k_{0}} and \tilde{n}^{\prime}_{k_{0}}=\tilde{n}^{\prime}_{k_{0}}-\tilde{n}^{\prime\prime}_{k_{0}} iii. If \tilde{n}^{\prime}_{k_{0}}=0 , then k_{0}=k_{0}+1 , else i=i+1 vii. return T and \tilde{S} Theorem 4 Given any sketch instance \tilde{I}=\{\langle\tilde{n}_{1},\tilde{p}_{1}\rangle, \langle\tilde{n}_{2},\tilde{p}_{2}\rangle,\cdots,\langle\tilde{n}_{t},\tilde{p}_{t}\rangle\} . A sketch schedule can be computed by the Modified Meta-algorithm in O(A(h(m,\delta),m,\delta)+m+t) time. Proof: It takes A(h(m,\epsilon),m,\delta) time at Step ii. We need O(m+t) steps to schedule the remaining jobs. This is because in each iteration when a machine M_{i} processes the jobs from \langle\tilde{n}_{k_{0}},\tilde{p}_{k_{0}}\rangle , for which the number of jobs from \langle\tilde{n}_{k},\tilde{p}_{k}\rangle is calculated and scheduled to M_{i} , either i or k_{0} is incremented until k_{0}=t and i is always no more than m . Therefore, the running time is O(A(h(m,\delta),m,\delta)+m+t) . Next, we show that the sketch schedule can be used to generate a schedule of all n jobs when all the information of all jobs are accessed. Theorem 5 Given an instance I , an (\alpha,\beta_{1},\beta_{2}) -sketch \tilde{I} and a sketch schedule \tilde{S} , we can generate a schedule S for instance I based on \tilde{S} and the makespan of S is at most ((1+\beta_{1})(1+\tfrac{\alpha}{1-\alpha}m)+\beta_{2})OPT(I) . Proof: Based on the sketch schedule \tilde{S} , we can construct a schedule S for the job instance I interval by interval. For each interval I_{k},\tilde{n}_{k}>0,1\leq k\leq t , by the definition of (\alpha,\beta_{1},\beta_{2}) -sketch, we have (1-\alpha)\,n_{k}\leq\tilde{n}_{k}\leq(1+\alpha)\,n_{k} , that is, |(n_{k}-\tilde{n}_{k})|\leq\alpha\cdot n_{k}\leq\tfrac{\alpha}{1-\alpha}\tilde{n}_{k}. To construct S , we try to schedule the jobs from I_{k} in the same way as in \tilde{S} . In the case of n_{k}>\tilde{n}_{k} , there will be at most \tfrac{\alpha}{1-\alpha}\tilde{n}_{k} jobs left unscheduled. We schedule these jobs to machine i that has the largest number of jobs from I_{k} scheduled, that is, \tilde{n}_{i,k} is the largest among all 1\leq i\leq m , which implies \tilde{n}_{i,k}\geq\tfrac{\tilde{n}_{k}}{m} . Combining all the intervals, it can be shown that the makespan of S is increased by at most \tfrac{\alpha}{1-\alpha}m times the makespan of \tilde{S} , which in turn is at most (1+\beta_{1})OPT(I) . For the intervals I_{k} with \tilde{n}_{k}=0 or k\geq t , we can schedule the jobs from these intervals on any machine, by definition of (\alpha,\beta_{1},\beta_{2}) -sketch, the makespan will increase by at most \beta_{2}OPT . In summary, the makespan of the constructed schedule is at most ((1+\beta_{1})(1+\tfrac{\alpha}{1-\alpha}m)+\beta_{2})OPT(I) . To summarize, we have shown that, for a given instance I , if we can obtain a (\alpha,\beta_{1},\beta_{2}) -sketch \tilde{I}=\{\langle\tilde{n}_{1},\tilde{p}_{1}\rangle, \langle\tilde{n}_{2},\tilde{p}_{2}\rangle,\cdots,\langle\tilde{n}_{t},\tilde{p}_{t}\rangle\} where t is sublinear in n , then we can get both an approximate value of OPT(I) and a sketch schedule in sublinear time. In the following, we will focus on designing sublinear time algorithms to obtain such an (\alpha,\beta_{1},\beta_{2}) -sketch for I . We first present some preliminaries. Then, we describe the algorithms in two sections, one for the case when the total number of job n is known, and one for when n is unknown. 3 Sublinear Time Algorithms for Obtaining the Sketch Instance 3.1 Preliminaries We provide preliminaries on proportional weighted random sampling and the generalized birthday paradox argument, which are the key tools used in our algorithms and their proofs. In addition, we use the well-known Chernoff bounds and union bound, which are given below for convenience. Chernoff Bounds: Let X_{1},\ldots,X_{n} be n independent random 0 - 1 variables and X=\sum_{i=1}^{n}X_{i} . i. If X_{i} takes 1 with probability at most p for i=1,\ldots,n , then for any \alpha>0 , \Pr(X>(1+\alpha)pn)<\left[{e^{\alpha}\over(1+\alpha)^{(1+\alpha)}}\right]^{pn} ; furthermore if 0<\alpha\leq 1 , \Pr(X>(1+\alpha)pn) \displaystyle e^{-\tfrac{(1+\delta)k(k-1)}{2n}-\tfrac{2(1+\delta)^{2}k^{3}}{3n^{2}}}>e^{-\tfrac{(1+\delta)k^{2}}{2n}-\tfrac{2(1+\delta)^{2}k^{3}}{3n^{2}}} Now we establish the upper bound of Pr_{n,k,\delta} . Since, w_{i}\leq w_{i+1} for 1\leq i\leq n-1 and w_{n}\leq(1+\delta)w_{1} , plugging into the upper bound of Lemma 1 , we get Pr_{n,k,\delta}\leq\prod_{j=1}^{k-1}\left(1-\tfrac{\sum_{i=1}^{j}{w_{i}}}{W}\right)\leq\prod_{j=1}^{k-1}\left(1-\tfrac{{w_{1}}\cdot j}{n\cdot(1+\delta)w_{1}}\right)\leq\prod_{j=1}^{k-1}\left(1-\tfrac{j}{n\cdot(1+\delta)}\right). Using the fact (1-x)\leq e^{-x} , we obtain Pr_{n,k,\delta}\leq\prod_{j=1}^{k-1}e^{-\tfrac{j}{n\cdot(1+\delta)}}=e^{-\sum_{j=1}^{k-1}\tfrac{j}{n\cdot(1+\delta)}}=e^{-\tfrac{(k-1)k}{2n\cdot(1+\delta)}}. For convenience, we let Pr_{ub}(n,k,\delta) and Pr_{lb}(n,k,\delta) denote the upper and lower bound of Pr_{n,k,\delta} from the above lemma, respectively. That is, Pr_{ub}(n,k,\delta)=e^{-\tfrac{(k-1)k}{2n(1+\delta)}} and Pr_{lb}(n,k,\delta)=e^{-\tfrac{(1+\delta)k^{2}}{2n}-\tfrac{2(1+\delta)^{2}k^{3}}{3n^{2}}}\kern 5.0pt. Next, we consider these two bounds of Pr_{n,k,\delta} , Pr_{ub}(n,k,\delta) and Pr_{lb}(n,k,\delta) , when the number of samples k is within a constant factor of \sqrt{n} . Lemma 3 Let {c} be a constant such that 4\leq{c}\leq\tfrac{1}{4\delta} , and n\geq\tfrac{1}{\delta^{2}} , then we have Pr_{lb}(n,\tfrac{\sqrt{n}}{(1+\delta)^{{c}}},\delta)\geq\tfrac{1}{(1-\delta)\sqrt{e}}\kern 5.0pt, (1) Pr_{ub}(n,(1+\delta)^{{c}}\sqrt{n},\delta)\leq\tfrac{1}{(1+\delta)\sqrt{e}}\kern 5.0pt, (2) Pr_{ub}(n,(1+\delta)^{{c}}\sqrt{n},\delta)\geq\tfrac{1}{e}\kern 5.0pt. (3) Proof: We first prove the inequality ( 1 ). Let the number of samples be k=\tfrac{\sqrt{n}}{(1+\delta)^{{c}}} . Plugging this into the definition of Pr_{lb}(n,k,\delta) , we get Pr_{lb}(n,\tfrac{\sqrt{n}}{(1+\delta)^{{c}}},\delta)=e^{-\tfrac{(1+\delta)^{1-2{c}}}{2}-\tfrac{2}{3\sqrt{n}(1+\delta)^{3{c}-2}}}\kern 5.0pt. By assumption, {c}\geq 4 and n\geq\tfrac{1}{\delta^{2}} , \sqrt{n}(1+\delta)^{3{c}-2}\geq\sqrt{n}\geq\tfrac{1}{\delta} . Thus, \displaystyle Pr_{lb}(n,\tfrac{\sqrt{n}}{(1+\delta)^{{c}}},\delta) \displaystyle= \displaystyle e^{-\tfrac{(1+\delta)^{1-2{c}}}{2}-\tfrac{2}{3\sqrt{n}(1+\delta)^{3{c}-2}}} \displaystyle\geq \displaystyle e^{-\tfrac{(1+\delta)^{1-2{c}}}{2}}\cdot e^{-\tfrac{2\delta}{3}} \displaystyle\geq \displaystyle e^{-\tfrac{1}{2}(1-(2{c}-1)\delta+(2{c}-1){c}\delta^{2})}\cdot e^{-\tfrac{2\delta}{3}} \displaystyle\geq \displaystyle e^{-\tfrac{1}{2}(1-{(2{c}-1)\delta}+\tfrac{(2{c}-1)\delta}{4})}\cdot e^{-\tfrac{2\delta}{3}}\hskip 28.90755pt\text{ by }{c}\leq\tfrac{1}{4\delta} \displaystyle\geq \displaystyle e^{-\tfrac{1}{2}(1-\tfrac{3(2{c}-1)\delta}{4})-\tfrac{2\delta}{3}} \displaystyle\geq \displaystyle e^{-\tfrac{1}{2}+\tfrac{15\delta}{8}}\hskip 72.26999pt\text{ by }{c}\geq 4 \displaystyle\geq \displaystyle\tfrac{1}{\sqrt{e}}\cdot(1+\tfrac{15\delta}{8})\hskip 43.36243pt\text{ by }e^{x}\geq 1+x \displaystyle\geq \displaystyle\tfrac{1}{\sqrt{e}(1-\delta)} Next, we prove the inequality ( 2 ). By definition of Pr_{ub}(n,k,\delta) , we have Pr_{ub}(n,k,\delta)=e^{-\tfrac{(k-1)k}{2n(1+\delta)}}\leq e^{-\tfrac{(k-1)^{2}}{2n(1+\delta)}}. Let k=(1+\delta)^{{c}}\sqrt{n} , and {c^{\prime}}={c}-1 , we have \displaystyle Pr_{ub}(n,(1+\delta)^{{c}}\sqrt{n},\delta) \displaystyle\leq \displaystyle e^{-\tfrac{((1+\delta)^{{c}}\sqrt{n}-1)^{2}}{2n(1+\delta)}} \displaystyle\leq \displaystyle e^{-\tfrac{((1+\delta)^{{c^{\prime}}}\sqrt{n})^{2}}{2n(1+\delta)}}\hskip 28.90755pt\text{ by }{c}={c^{\prime}}+1\text{ and }n\geq\tfrac{1}{\delta^{2}} \displaystyle= \displaystyle e^{-\tfrac{(1+\delta)^{2{c^{\prime}}-1}}{2}} \displaystyle\leq \displaystyle e^{-\tfrac{1+(2{c^{\prime}}-1)\delta}{2}}\hskip 28.90755pt\text{ by }(1+\delta)^{x}\geq\delta x\text{ for }\delta>0\text{ and }x\geq 0 \displaystyle\leq \displaystyle e^{-\tfrac{1}{2}}\cdot e^{-\tfrac{(2{c^{\prime}}-1)\delta}{2}} \displaystyle\leq \displaystyle e^{-\tfrac{1}{2}}\cdot(1-\tfrac{1}{2}\tfrac{(2{c^{\prime}}-1)\delta}{2})\hskip 7.22743pt\text{ by }{c}\leq\tfrac{1}{4\delta}\text{ and }e^{-x}\leq 1-\tfrac{x}{2}\text{ if }x<1 \displaystyle\leq \displaystyle\tfrac{1}{\sqrt{e}}(1-\tfrac{5\delta}{4})\hskip 72.26999pt\text{ by }{c}\geq 4\text{ and }{c^{\prime}}={c}-1 \displaystyle\leq \displaystyle\tfrac{1}{\sqrt{e}(1+\delta)}\kern 5.0pt. On the other hand, we have Pr_{ub}(n,k,\delta)=e^{-\tfrac{k(k-1)}{2n(1+\delta)}}\geq e^{-\tfrac{k^{2}}{2n(1+\delta)}} . Let k=(1+\delta)^{{c}}\sqrt{n} , we get \displaystyle Pr_{ub}(n,(1+\delta)^{{c}}\sqrt{n},\delta) \displaystyle\geq \displaystyle e^{-\tfrac{(1+\delta)^{2{c}-1}}{2}} \displaystyle\geq \displaystyle e^{-\tfrac{1}{2}(1+\delta)^{\tfrac{1}{2\delta}}}\hskip 14.45377pt\text{ by }{c}\leq\tfrac{1}{4\delta} \displaystyle\geq \displaystyle e^{-\tfrac{1}{2}\sqrt{e}}\hskip 28.90755pt\text{ by }\ \ (1+\delta)^{\tfrac{1}{\delta}}{(1+\delta)^{{c}+1}}{\sqrt{n_{k}}} . First, we consider the probability of l_{k}<\tfrac{\sqrt{n_{k}}}{{(1+\delta)^{{c}}}} . From Step 2. 2.i. 2.(i.)iv. of the algorithm, we know that if g_{l,k}<\tfrac{1}{\sqrt{e}}u in an iteration 1\leq l<\tfrac{\sqrt{n_{k}}}{{(1+\delta)^{{c}}}} , then we have \tilde{n}_{k}=l^{2} and l_{k}=l<\tfrac{\sqrt{n_{k}}}{{(1+\delta)^{{c}}}} . Thus, Pr(l_{k}<\tfrac{\sqrt{n_{k}}}{{(1+\delta)^{{c}}}})\leq\sum_{l}Pr(g_{l,k}<\tfrac{1}{\sqrt{e}}u) where l\leq\tfrac{\sqrt{n_{k}}}{{(1+\delta)^{{c}}}} . Since l grows geometrically and l\leq 3\sqrt{n} , the number of such iterations is at most \log_{1+\delta}3\sqrt{n} . Thus, Pr(l_{k}<\tfrac{\sqrt{n_{k}}}{(1+\delta)^{{c}}})\leq(\log_{1+\delta}3\sqrt{n})Pr(g_{l,k}\leq\tfrac{1}{\sqrt{e}}u)\kern 5.0pt. (7) Now, let us bound Pr(g_{l,k}\leq\tfrac{1}{\sqrt{e}}u) in a particular iteration l . Recall that g_{l,k} is the number of sample groups in which the first l samples are all distinct. By inequality ( 1 ), the probability that the first l elements in a particular group are all distinct is greater than p_{l}=Pr_{lb}(n_{k},\tfrac{\sqrt{n_{k}}}{{{(1+\delta)^{{c}}}}},\delta)\geq\tfrac{1}{(1-\delta)\sqrt{e}}\kern 5.0pt. (8) Thus, we have \tfrac{1}{\sqrt{e}}u\leq(1-\delta)p_{l}u . In addition, since the number of samples in I_{k} is at least (see line ( 2.d. ) of Sketch-Algorithm) \tfrac{\delta K}{mh}=\tfrac{\delta}{mh}\tfrac{36m}{\delta^{4}}\sqrt{n}\cdot\tau(n)=\tfrac{36}{\delta^{3}h}\sqrt{n}\cdot\tau(n), and each group has 3\sqrt{n} samples, the number of groups u satisfies the following inequality u\geq\tfrac{12}{\delta^{3}h}\cdot\tau(n)\geq\tfrac{12}{\delta^{2}}\cdot\ln(16h(\log_{1+\delta}3\sqrt{n})/\gamma_{0})\kern 5.0pt. (9) Applying the Chernoff bound to the random variable g_{l,k} with p_{l} and \delta , we have \displaystyle Pr(g_{l,k}\leq\tfrac{1}{\sqrt{e}}u) \displaystyle\leq \displaystyle Pr(g_{l,k}<(1-\delta)p_{l}u) \displaystyle\leq \displaystyle e^{-\tfrac{\delta^{2}}{2}p_{l}u} \displaystyle\leq \displaystyle e^{-\tfrac{\delta^{2}}{2\sqrt{e}}u}\hskip 86.72377pt\text{ by (\ref{bound-of-pl})} \displaystyle\leq \displaystyle e^{-\ln(16h(\log_{1+\delta}3\sqrt{n})/\gamma_{0})}\hskip 21.68121pt\text{ by (\ref{bound-of-u})} \displaystyle\leq \displaystyle\tfrac{\gamma_{0}}{16h(\log_{1+\delta}3\sqrt{n})}\kern 5.0pt. Plugging into ( 7 ), Pr(l_{k}<\tfrac{\sqrt{n_{k}}}{(1+\delta)^{{c}}})\leq(\log_{1+\delta}3\sqrt{n})Pr(g_{l,k}\leq\tfrac{1}{\sqrt{e}}u)\leq\tfrac{\gamma_{0}}{16h}\kern 5.0pt. Now, we consider the probability of l_{k}>{(1+\delta)^{{c}+1}}{\sqrt{n_{k}}} . From Step 2. 2.i. 2.(i.)iv. of the algorithm, we know this happens only if g_{l,k}\geq\tfrac{1}{\sqrt{e}}u for all iterations l\leq{(1+\delta)^{{c}+1}}{\sqrt{n_{k}}} . In particular, this is true for the l where (1+\delta)^{{c}}\sqrt{n_{k}}{(1+\delta)^{{c}+1}}{\sqrt{n_{k}}})\leq Pr(g_{l,k}\geq\tfrac{1}{\sqrt{e}}u)\kern 5.0pt. Additionally, since l>(1+\delta)^{{c}}\sqrt{n_{k}} , we have Pr_{ub}(n_{k},l,\delta){(1+\delta)^{{c}+1}}{\sqrt{n_{k}}}) \displaystyle\leq \displaystyle Pr(g_{l,k}\geq\tfrac{1}{\sqrt{e}}u) \displaystyle\leq \displaystyle Pr(g_{l,k}\geq(1+\delta)p_{r}u) \displaystyle\leq \displaystyle e^{-\tfrac{\delta^{2}}{3}p_{r}u}\hskip 21.68121pt\text{by Chernoff bound for $g_{l,k}$} \displaystyle\leq \displaystyle e^{-\tfrac{\delta^{2}}{9}u}\hskip 28.90755pt(p_{r}\geq\tfrac{1}{e}>\tfrac{1}{3}) \displaystyle\leq \displaystyle e^{-\tfrac{\delta^{2}}{9}\cdot\tfrac{12}{\delta^{2}}\cdot\ln(16h(\log_{1+\delta}3\sqrt{n})/\gamma_{0})}\leq\tfrac{\gamma_{0}}{16h}\hskip 14.45377pt\text{by inequality (\ref{bound-of-u})}\kern 5.0pt. Combining the above two cases, for a particular interval I_{k} , we get Pr(l_{k}\notin[\tfrac{\sqrt{n_{k}}}{{{(1+\delta)^{{c}}}}},(1+\delta)^{{c}+1}\sqrt{n_{k}}])\leq Pr(l_{k}<\tfrac{\sqrt{n_{k}}}{(1+\delta)^{{c}}})+Pr(l_{k}>{\sqrt{n_{k}}}{(1+\delta)^{{c}+1}})\leq\tfrac{\gamma_{0}}{8h}\kern 5.0pt. Applying union bound to all h intervals, we have Pr(l_{k}\notin[\tfrac{\sqrt{n_{k}}}{{{(1+\delta)^{{c}}}}},(1+\delta)^{{c}+1}\sqrt{n_{k}}])\leq\tfrac{\gamma_{0}}{8}. From Lemma 5 , and 6 , we can get the following. Theorem 6 For all intervals I_{k} where \langle\tilde{n}_{k},\tilde{p}_{k}\rangle\in\tilde{I} , the probability that \tilde{n}_{k}\in[(1+\delta)^{-2{c}}\cdot n_{k},(1+\delta)^{2{c}+2}\cdot n_{k}]) where {c}=4 , is at least 1-\tfrac{9}{8}\gamma_{0} . Theorem 6 tells us that given an instance I , \tilde{I} provides a good approximation for the number of jobs in the intervals of H . In the following, we prove that \tilde{I} also provides a good approximation for the makespan of the original instance I . During the construction of \tilde{I} from I , the Sketch-Algorithm introduces error in three ways: (1) we discard jobs from intervals I_{k} , k>h ; (2) we discard jobs from intervals I_{k} where k\leq h and X_{k}<\frac{\delta}{mh}\cdot K ; and (3) for all the intervals I_{k}\in H , the processing times of the jobs are rounded up by a factor of at most \frac{1}{1-\delta}\leq({1+\delta}) , We will show that the error introduced in each case is small. Lemma 7 The total processing time of jobs in the interval I_{k} with k>h , is at most 2\delta OPT . Proof: If j is a job in I_{k} , k>h , then its processing time p_{j} is at most p^{\prime}_{max}(1-\delta)^{h}\leq 2np^{\prime}(1-\delta)^{h} where p^{\prime} is the maximum processing time among the K_{0} samples (see line 1.a. ). There are at most n such jobs, and their total processing time is at most n\cdot 2n(1-\delta)^{h}p^{\prime}\leq 2n^{2}\cdot e^{-\delta h}p^{\prime}\leq 2n^{2}\cdot e^{-\delta h}OPT, which is at most 2\delta OPT since h=\tfrac{1}{\delta}\ln\tfrac{n^{2}}{\delta} Lemma 8 With probability at least 1-\gamma_{0} , the total processing time of jobs from the intervals I_{k} , 1\leq k\leq h and X_{k}<\frac{\delta}{mh}\cdot K , is at most 2\delta\text{OPT} . Proof: Let I_{k} be an interval with 1\leq k\leq h and X_{k}<\frac{\delta}{mh}\cdot K . Let P(I_{k}) be the total processing time of jobs in I_{k} . We prove that P(I_{k})\leq\frac{2\delta}{mh}P with high probability. Suppose that P(I_{k})\geq\frac{2\delta}{mh}P . Then, the probability that a sample is from I_{k} is at least \tfrac{2\delta}{mh} . When there are K samples, applying Chernoff bound, we get Pr(X_{k}<\frac{\delta}{mh}\cdot K)=Pr(X_{k}<(1-{1\over 2})\cdot\frac{2\delta}{mh}\cdot K)\leq e^{-\tfrac{1}{2}\left(\tfrac{1}{2}\right)^{2}\tfrac{2\delta}{mh}K}=e^{-\tfrac{{\delta}}{4mh}K} . Using union bound on all h intervals, we get the probability that there exists an I_{k} such that P(I_{k})\geq\frac{2\delta}{mh}P and X_{k}<\frac{\delta}{mh}\cdot K is at most h\cdot e^{-\tfrac{\delta}{4mh}K}\leq h\cdot e^{-(\tfrac{\delta}{4mh}\cdot\tfrac{36m}{\delta^{4}}\sqrt{n}\cdot\tau(n))}\\ \leq h\cdot e^{-(\tfrac{9}{h\delta^{3}}\sqrt{n}\cdot\tau(n))}\leq h\cdot{\gamma_{0}\over h}\leq\gamma_{0}\kern 5.0pt. Therefore, with probability at least 1-\gamma_{0} , P(I_{k})<\frac{2\delta}{mh}P for all I_{k} where X_{k}<\frac{\delta}{mh}\cdot K . The total processing time of the intervals where X_{k}<\tfrac{\delta}{mh}K is at most h\cdot\tfrac{2\delta}{mh}P=2\delta\tfrac{P}{m}\leq 2\delta OPT\kern 5.0pt. Lemma 9 Let I^{\prime} be the instance corresponding to \tilde{I} such that for any interval pair \langle\tilde{n}_{k},\tilde{p}_{k}\rangle\in\tilde{I} , there is an interval pair \langle n_{k},\tilde{p}_{k}\rangle\in I^{\prime} . Then (1-2{c}m\delta)OPT(I^{\prime})\leq OPT(\tilde{I})\leq(1+6{c}m\delta)OPT(I^{\prime}) for \delta\leq\tfrac{1}{4{c}} and {c}=4 . Proof: The difference of I^{\prime} and \tilde{I} lies in the number of jobs. By Theorem 6 , n_{k}(1+\delta)^{-2{c}}\leq\tilde{n}_{k}\leq(1+\delta)^{2{c}+2}n_{k} . Let S^{\prime} and \tilde{S} be an optimal schedule for I^{\prime} and \tilde{I} , respectively. Let P^{\prime} be the total processing time of all jobs in I^{\prime} , that is, P^{\prime}=\sum_{k}n_{k}\tilde{p}_{k} . Comparing S^{\prime} and \tilde{S} , for each interval I_{k} , we have two cases. In the first case, n_{k}\leq\tilde{n}_{k} . Using the fact \delta\leq\tfrac{1}{4{c}} and {c}=4 , we have (\tilde{n}_{k}-n_{k})\leq[(1+\delta)^{2{c}+2}-1]n_{k}\leq(2{c}+2)\delta\cdot\sum_{i\geq 1}\tfrac{1}{i!}\cdot n_{k}\leq 3c\delta\cdot(e-1)\cdot n_{k}\leq 6{c}\delta n_{k}. In the second case, \tilde{n}_{k}\leq n_{k} . We have (n_{k}-\tilde{n}_{k})\leq[1-(1+\delta)^{-2{c}}]n_{k}\leq[1-(1-\delta)^{2{c}}]n_{k}\leq 1-(1-2{c}\delta)n_{k}\leq 2{c}\delta n_{k}. Combining all the intervals, the makespan of \tilde{S} is greater than that of S^{\prime} by no more than 6{c}\delta P^{\prime} and less than that of S^{\prime} by at most 2{c}\delta P^{\prime} . Since OPT(I^{\prime})\geq P^{\prime}/m , we get (1-2{c}m\delta)OPT(I^{\prime})\leq OPT(\tilde{I})\leq(1+6{c}m\delta)OPT(I^{\prime}) . Note that from I to I^{\prime} , the processing times of jobs are rounded up by a factor of at most (1+\delta) . This will increase the optimal makespan by a factor of at most \delta . In addition, we discard jobs from intervals not in H whose total processing time is at most 4\delta OPT(I) by Lemmas 7 and 8 . Thus, we have (1-4\delta)OPT(I)h}X_{k}\leq\frac{\delta{K}}{4m}=\tfrac{d_{0}}{4} b. let K_{0}=\tfrac{8}{\beta_{0}}\cdot\ln\tfrac{e}{\beta_{0}\gamma_{0}} where \beta_{0}=\tfrac{\delta^{3}}{32mh} c. draw K_{0} random samples d. let H be the set of intervals H=\{I_{k}:1\leq k\leq h,\text{and }X_{k}\geq\tfrac{\delta}{mh}\cdot{K_{0}}\} e. let H_{1}=\{I_{k}:I_{k}\in H,\text{ and }\exists j , j\in I_{k} and x_{j}\geq 8\beta_{0}K_{0}\} , and H_{2}=H\setminus H_{1} f. let \tilde{I_{1}}=\tilde{I_{2}}=\emptyset g. for each interval I_{k}\in H_{1} let \tilde{n}_{k} be the number of sampled jobs from I_{k} \tilde{I_{1}}=\tilde{I_{1}}\cup\{\langle\tilde{n}_{k},\tilde{p}_{k}\rangle\} h. for each interval I_{k}\in H_{2} let gs_{k}=1 i. let j=1 j. while there exists I_{k}\in H_{2} that are not marked I. discard the current samples, draw K_{j}=2^{j}K_{0} new samples II. for each unmarked interval I_{k} i. find the largest integer t such that X_{k}\geq l_{t}\cdot u_{t} where l_{t}=(1+\delta)^{t} , u_{t}=\lceil\tfrac{3{e}}{\delta^{2}}(\ln\tfrac{1}{\gamma_{t}})\rceil and \gamma_{t}=\tfrac{\delta}{hl_{t}}\gamma_{0} ii. partition the samples in I_{k} evenly into u_{t} groups G_{1},\cdots,G_{u_{t}} iii. for i=gs_{k} , i\leq t and I_{k} still unmarked, i=i+1 let l_{i}=(1+\delta)^{i} , \gamma_{i}=\tfrac{\delta}{hl_{i}}\gamma_{0} , and u_{i}=\lceil\tfrac{3{e}}{\delta^{2}}(\ln\tfrac{1}{\gamma_{i}})\rceil let g_{l_{i},k} be the number of groups among G_{1},\cdots,G_{u_{t}} where the first l_{i} samples in the group are all distinct if g_{l_{i},k}\leq\tfrac{1}{\sqrt{e}}u_{i} let \tilde{n}_{k}=l_{i}^{2} let \tilde{I_{2}}=\tilde{I_{2}}\cup\{\langle\tilde{n}_{k},\tilde{p}_{k}\rangle\} mark I_{k} iv. if I_{k} is still unmarked, gs_{k}=t III. j=j+1 k. \tilde{I}=\tilde{I_{1}}\cup\tilde{I_{2}} The analysis of the algorithm and its generated sketch \tilde{I} is quite involved. We proceed as follows. First, we show that, with high probability, w_{0} provides a good bound in the sense that the total processing time of all jobs with processing times greater than w_{0} has small impact on estimating OPT . Then we show that the number of intervals in H is bounded by h=O(\log mn) . For all the intervals in H_{1} and H_{2} , we will show that the algorithm computes a good estimate of the number of jobs in each interval of H_{1} and H_{2} . Consequently, we can get a good estimation of OPT through the sketch instance \tilde{I} . Finally, we show that the total number of samples drawn by the algorithm is sublinear. The detailed analysis is presented subsequent subsections. 3.3.1 \sum_{p_{j}>w_{0}}p_{j}\leq\delta OPT and h=O(\log{mn}) Lemma 10 Let w_{\delta} be the smallest processing time among all jobs such that \sum_{p_{j}>w_{\delta}}p_{j}\leq{\delta P\over m} . Then, with probability at least 1-\gamma_{0} , w_{0}\geq w_{\delta} , which implies \sum_{p_{j}>w_{0}}p_{j}\leq\delta OPT . Proof: Assume that w_{0}w_{0}}p_{j}>{\delta P\over m} . Therefore, the probability of sampling a job with processing time less than or equal to w_{0} is at most (1-\tfrac{\delta}{m}) . Since w_{0} is the largest processing time among all K samples, all these samples have a processing time at most w_{0} . However, the probability of this happening is at most (1-\tfrac{\delta}{m})^{{K}} . By the choice of {K} and d_{0} in step 1. 1.a. of the algorithm, (1-\tfrac{\delta}{m})^{{K}}=(1-\tfrac{\delta}{m})^{\tfrac{m}{\delta}d_{0}}\leq\gamma_{0}\kern 5.0pt. Thus, with probability of at least 1-\gamma_{0} , we have w_{0}\geq w_{\delta} . Consequently, \sum_{p_{j}>w_{0}}p_{j}\leq\sum_{p_{j}>w_{\delta}}p_{j}\leq{\delta P\over m}\leq\delta OPT , since \frac{P}{m}\tfrac{1}{\delta}\ln{\tfrac{8nm}{\delta(1-\delta)}} . Proof: Let h_{1} be the largest index of the processing time intervals such that (\sum_{j\in I_{t},t\geq h_{1}}p_{j})>{\delta P\over 8m} . We first show that h_{1}<{1\over\delta}\ln{8nm\over\delta} . If a job j\in I_{t}=(\tilde{p}_{t+1},\tilde{p}_{t}] where t\geq h_{1} , then p_{j}\leq\tilde{p}_{t}\leq\tilde{p}_{h_{1}}=(1-\delta)^{h_{1}-1}w_{0} . Therefore, we can bound the total processing time of the jobs in the intervals I_{t} , t\geq h_{1} , \sum_{j\in I_{t},t\geq h_{1}}p_{j}\leq n\cdot(1-\delta)^{h_{1}-1}w_{0}\leq\tfrac{n}{(1-\delta)}\cdot e^{-\delta h_{1}}P\kern 5.0pt. By the definition of h_{1} , we must have \frac{\delta P}{8m}<\sum_{j\in I_{t},t\geq h_{1}}p_{j}\leq\tfrac{n}{(1-\delta)}e^{-\delta h_{1}}\cdot P\kern 5.0pt, from which we get h_{1}<{1\over\delta}\ln\tfrac{8nm}{\delta(1-\delta)} . Now, assume h>h_{1} . Then, by definition of h_{1} , we must have \sum_{p_{j}\in I_{t},t\geq h}p_{j}\leq{\delta P\over 8m} . Applying Chernoff bound with \alpha=1 and p={\delta\over 8m} , we get, with probability at most e^{-\frac{1}{3}(1)^{2}\frac{\delta}{8m}{K}}\leq e^{-\frac{1}{24}d_{0}}<(1-\tfrac{1}{6})^{\tfrac{1}{6}d_{0}}\leq(1-\tfrac{\delta}{m})^{\tfrac{\delta}{m}d_{0}}\leq\gamma_{0}\kern 5.0pt, the number of samples from intervals I_{t} , t\geq h , is more than (1+1)\cdot{\delta\over 8m}{K}={\delta\over 4m}{K} . On the other hand, by Step 2. 2.a. of the algorithm, h is the smallest integer such that \sum_{k>h}X_{k}\leq\frac{\delta{K}}{4m} , which implies that the number of samples from I_{t} for all t\geq h , including the interval I_{h} must be more than \frac{\delta{K}}{4m} . Thus, the probability that h>h_{1}>\tfrac{1}{\delta}\ln{\tfrac{8nm}{\delta(1-\delta)}} is at most \gamma_{0} . 3.3.2 Intervals in H_{1} : \tilde{n}_{k} as an Approximation of {n}_{k} We first present a technical lemma that is used in the proofs of several other lemmas. Lemma 12 For each k\geq K_{0} , \beta\geq{\beta_{0}} , and a\geq e^{\tfrac{1}{8}} , we have {1\over\beta}a^{-\beta k}\leq{\gamma_{0}\over e} , where K_{0} and \beta_{0} are defined in Adaptive-Sketch-Algorithm. Proof: It is obvious {1\over\beta}a^{-\beta k}\leq{1\over\beta_{0}}(e^{\tfrac{1}{8}})^{-\beta_{0}K_{0}} , and by the definition of K_{0} at Step 2.b. of the algorithm, we have {1\over\beta}a^{-\beta k}\leq{1\over\beta_{0}}(e^{\tfrac{1}{8}})^{-\beta_{0}K_{0}}={1\over\beta_{0}}(e^{\tfrac{1}{8}})^{-\beta_{0}\cdot{8\over\beta_{0}}\cdot\ln{e\over\beta_{0}\gamma_{0}}}={\gamma_{0}\over e}\kern 5.0pt. Lemma 13 and Lemma 14 are applications of Chernoff bound. These lemmas demonstrate that when we draw samples using weighted sampling, if a job has a large processing time, it is unlikely to be sampled only a few times; conversely, if a job has a small processing time, it is unlikely to be sampled many times. Lemma 13 Assume that k samples are drawn. The probability that there exists a job j such that p_{j}\geq\beta_{1}P but x_{j}<(1-\alpha)\beta_{1}k , is at most {1\over\beta_{1}}e^{-{\tfrac{1}{2}}\alpha^{2}\beta_{1}k} . Furthermore, if k\geq K_{0} , \alpha\geq{1\over 2} and \beta_{1}=\beta_{0} , the probability is at most \gamma_{0} . Proof: Let j be a job with p_{j}\geq\beta_{1}P . If we draw a single sample, the probability of selecting job j is at least \beta_{1} . When drawing k samples, by Chernoff bound, the probability that the number of occurrences of job j is less than (1-\alpha)\beta_{1}k is Pr(x_{j}<(1-\alpha)\beta_{1}k)\leq e^{-{1\over 2}\alpha^{2}\beta_{1}k} . Given that there can be at most {1\over\beta_{1}} jobs with processing time at least \beta_{1}P , by union bound, the probability that there exists at least one job j with p_{j}\geq\beta_{1} but x_{j}<(1-\alpha)\beta_{1}k , is at most v_{1}={1\over\beta_{1}}e^{-{1\over 2}\alpha^{2}\beta_{1}k}={1\over\beta_{1}}(e^{{1\over 2}\alpha^{2}})^{-\beta_{1}k} . If \alpha\geq{1\over 2} , then e^{{1\over 2}\alpha^{2}}\geq e^{\tfrac{1}{8}} . In addition, if k\geq K_{0} , and \beta_{1}=\beta_{0} , by Lemma 12 , we have v_{1}={1\over\beta_{1}}(e^{{1\over 2}\alpha^{2}})^{-\beta_{1}k}\leq{1\over\beta_{1}}e^{-\tfrac{1}{8}{\beta_{1}k}}\leq{\gamma_{0}\over e}\leq\gamma_{0}. Lemma 14 Let k be an integer, and \beta_{2}\in(0,1) such that \beta_{2}k\geq 1 . Assume that k samples are drawn. Then the probability that there exists a job j such that p_{j}\leq\beta_{2}P and x_{j}\geq 4\beta_{2}k , is at most {e\over\beta_{2}}\cdot({e\over 4})^{\beta_{2}k} . Furthermore, if k\geq K_{0} , and \beta_{2}=2\beta_{0} , then the probability is at most \gamma_{0} . Proof: We examine the jobs in order of their processing times and use the following Chenoff bound: Pr(x_{i}>(1+\alpha)pk)<\left[{e^{\alpha}\over(1+\alpha)^{(1+\alpha)}}\right]^{pk}<\left[{e\over(1+\alpha)}\right]^{\alpha\cdot pk}\kern 5.0pt. (10) Consider jobs j such that \tfrac{1}{2^{i}}\beta_{2}P(1+\alpha)pk)=Pr(x_{j}>4\beta_{2}k)<\left(\tfrac{e}{2^{i+1}}\right)^{(2^{i+1}-1)\cdot\tfrac{1}{2^{i-1}}\beta_{2}k}<\left(\tfrac{e}{2^{i+1}}\right)^{2\beta_{2}k}. Using union bound, the probability that there exists at least one such job in this interval that is sampled more than 4\beta_{2}k times is at most \displaystyle\tfrac{2^{i}}{\beta_{2}}\cdot\left(\tfrac{e}{2^{i+1}}\right)^{2\beta_{2}k} \displaystyle\leq \displaystyle\tfrac{2^{i}}{\beta_{2}}\cdot\left(\tfrac{e}{2^{i+1}}\right)\left(\tfrac{e}{2^{i+1}}\right)^{\beta_{2}k} \displaystyle\leq \displaystyle{e\over 2\beta_{2}}\cdot\left(\tfrac{e}{2^{i+1}}\right)^{\beta_{2}k} \displaystyle= \displaystyle{e\over 2\beta_{2}}\cdot\left(\tfrac{e}{4}\right)^{\beta_{2}k}\cdot(\tfrac{1}{2^{i-1}})^{\beta_{2}k} Apply union bound to all processing time intervals (\tfrac{1}{2^{i}}\beta_{2}P,\tfrac{1}{2^{i-1}}\beta_{2}P] , i\geq 1 , we get the probability that there exists at least one job whose processing time is less than \beta_{2}P but sampled more than 4\beta_{2}k ( \beta_{2}k\geq 1 ) times is at most v_{2}=\sum_{i=1}^{+\infty}{e\over 2\beta_{2}}\cdot\left(\tfrac{e}{4}\right)^{\beta_{2}k}\cdot(\tfrac{1}{2^{i-1}})^{\beta_{2}k}\leq{e\over 2\beta_{2}}\cdot\left(\tfrac{e}{4}\right)^{\beta_{2}k}\cdot 2={e\over\beta_{2}}\cdot\left(\tfrac{4}{e}\right)^{-\beta_{2}k}\kern 5.0pt. Since \beta_{2}=2\beta_{0} , and \tfrac{4}{e}>e^{\tfrac{1}{8}} , if k\geq K_{0} (see line ( 2.b. ) of Adaptive-Sketch-Algorithm), by Lemma 12 , we have \displaystyle v_{2} \displaystyle= \displaystyle{e\over\beta_{2}}\cdot\left({4\over e}\right)^{-\beta_{2}k}=e\cdot\left({1\over\beta_{2}}\cdot\left({4\over e}\right)^{-\beta_{2}k}\right)\leq e\cdot{\gamma_{0}\over e}\leq\gamma_{0}. With the previous two lemmas, we can show that for each interval in H_{1} , with high probability, all jobs from the interval are sampled, allowing us to get the exact number of jobs in it. Lemma 15 With probability at least (1-2\gamma_{0}) , \tilde{n}_{k}={n}_{k} for all k , I_{k}\in H_{1} . Proof: By construction, for each \langle\tilde{n}_{k},\tilde{p}_{k}\rangle\in\tilde{I_{1}} , there exists a job j\in I_{k} such that x_{j}\geq 8\beta_{0}K_{0} . By Lemma 14 , the probability that p_{j}\geq 2\beta_{0}P is at least 1-\gamma_{0} . Next, assume that p_{j}\geq 2\beta_{0}P . We show that, with high probability, all jobs in any interval containing at least one of those jobs j are also sampled. By definition of intervals, if a job r is in the same interval as job j , p_{r}\geq p_{j}(1-\delta) . Since \delta<\tfrac{1}{2} , if p_{j}\geq 2\beta_{0}P , then p_{r}\geq(1-\delta)p_{j}\geq p_{j}/2\geq\beta_{0}P. When k , k>K_{0} , samples are drawn, by Lemma 13 , the probability that there exists a job r such that p_{r}\geq\beta_{0}P and x_{r}<\beta_{0}k/2 is at most \gamma_{0} . In conclusion, the probability that there exists a k such that \langle\tilde{n}_{k},\tilde{p}_{k}\rangle\in\tilde{I_{1}} and \tilde{n}_{k}\neq n_{k} is at most 2\gamma_{0} . 3.3.3 Intervals in H_{2} : \tilde{n}_{k} as an Approximation of {n}_{k} Intuitively, an interval from H_{2} does not contain jobs with processing times large enough to be sampled as frequently as those from intervals in H_{1} , but it contains a large number of jobs. We show that our algorithm provides an approximation for the number of jobs in each I_{k}\in H_{2} based on the principal of birthday-paradox. For a particular I_{k}\in H_{2} , let F_{i,k} be the event that, at the end of an iteration of Step 2. 2.j. 2.(j.)II. 2.II.iii. , either l_{i}<(1+\delta)^{-{c}}\cdot\sqrt{n_{k}} and I_{k} is marked, or l_{i}\geq(1+\delta)^{{c}}\cdot\sqrt{n_{k}} and I_{k} is remains unmarked. Lemma 16 For a given I_{k}\in H_{2} and i\geq 1 , Pr(F_{i,k})<\gamma_{i} Proof: First, we consider the probability of I_{k} is marked at the end of an of Step 2. 2.j. 2.(j.)II. 2.II.iii. , where l_{i}\leq(1+\delta)^{-{c}}\cdot\sqrt{n_{k}} . For a specific group, the probability that the first l_{i} samples are all distinct in a group G_{j} is at least Pr_{lb}(n_{k},l_{i},\delta)\geq Pr_{lb}(n_{k},\tfrac{\sqrt{n_{k}}}{{{(1+\delta)^{{c}}}}},\delta) . Let p_{L}=Pr_{lb}(n_{k},\tfrac{\sqrt{n_{k}}}{{{(1+\delta)^{{c}}}}},\delta) . By the inequality ( 1 ) from the preliminary section, we have p_{L}\geq\tfrac{1}{(1-\delta)\sqrt{e}} . Thus Pr(g_{l_{i},k}\leq\tfrac{1}{\sqrt{e}}u_{i})\leq Pr(g_{l_{i},k}\leq(1-\delta)p_{L}u_{i}). Applying Chernoff bound with p=p_{L} to all u_{i} groups, we get Pr(g_{l_{i},k}\leq\tfrac{1}{\sqrt{e}}u_{i})\leq Pr(g_{l_{i},k}<(1-\delta)p_{L}u_{i})\leq e^{-\delta^{2}p_{L}u_{i}/3}\kern 5.0pt. Note that p_{L}\geq\tfrac{1}{\sqrt{e}} , and by the definition of u_{i} in Step 2. 2.j. 2.(j.)II. 2.II.iii. of the algorithm, we have Pr(g_{l_{i},k}\leq\tfrac{1}{\sqrt{e}}u_{i})\leq e^{-\delta^{2}p_{L}u_{i}/3}\leq e^{-\delta^{2}\cdot\tfrac{1}{\sqrt{e}}(-\tfrac{3{e}\ln\gamma_{i}}{\delta^{2}}){1\over 3}}\leq e^{\tfrac{1}{\sqrt{e}}e\ln{\gamma_{i}}}\leq\gamma_{i}\kern 5.0pt. Now, we consider the probability that I_{k} is not marked in iteration i and l_{i}>{(1+\delta)^{{c}}}{\sqrt{n_{k}}} . The probability that the first l_{i} samples are all distinct in a group G_{j} is at most P_{u}(n_{k},l_{i},\delta)\leq P_{u}(n_{k},(1+\delta)^{{c}}\sqrt{n_{k}},\delta) . Let p_{R}=P_{u}(n_{k},(1+\delta)^{{c}}\sqrt{n_{k}},\delta) . By inequality ( 2 ) from the preliminary section, p_{R}\leq\tfrac{1}{(1+\delta)\sqrt{e}} . Therefore, we get Pr(g_{l_{i},k}\geq\tfrac{1}{\sqrt{e}}u_{i})\leq Pr(g_{l_{i},k}\geq(1+\delta)p_{R}u_{i})\kern 5.0pt. Applying Chernoff bound with p=p_{R} to all u_{i} groups, Pr(g_{l_{i},k}\geq\tfrac{1}{\sqrt{e}}u_{i})\leq Pr(g_{l_{i},k}>(1+\delta)p_{R}u_{i})\leq e^{-\delta^{2}p_{R}u_{i}/3}\kern 5.0pt. By inequality ( 3 ), we have p_{R}\geq\tfrac{1}{e} . And by the definition of u_{i} in the algorithm, we have Pr(g_{l_{i},k}\geq\tfrac{1}{\sqrt{e}}u_{i})\leq e^{-\delta^{2}p_{R}\cdot u_{i}/3}\leq e^{-\delta^{2}\cdot\tfrac{1}{e}\cdot(-\tfrac{3{e}\ln\gamma_{i}}{\delta^{2}})\cdot{1\over 3}}\leq e^{\tfrac{1}{e}e\ln{\gamma_{i}}}\leq\gamma_{i}\kern 5.0pt. Combining the above two cases, we proved the lemma. Lemma 17 The probability that there exists an interval I_{k} such that \langle\tilde{n}_{k},\tilde{p}_{k}\rangle\in\tilde{I_{2}} and \tilde{n}_{k}\notin[(1+\delta)^{-2{c}}\cdot n_{k},(1+\delta)^{2{c}}\cdot n_{k})]) where {c}=4 , is at most \gamma_{0} . Proof: For a particular interval I_{k}\in\tilde{I_{2}} , the probability that \tilde{n}_{k}\notin[(1+\delta)^{-2{c}}\cdot n_{k},(1+\delta)^{2{c}}\cdot n_{k})]) is \sum_{i}Pr(F_{i,k})<\sum_{i}\gamma_{i} . There are at most h intervals in H . The probability that there exists one such interval is at most h\sum_{i}\gamma_{i}=h\sum_{i}\tfrac{\delta\gamma_{0}}{hl_{i}}=\delta\gamma_{0}\sum_{i\geq 1}{1\over(1+\delta)^{i}}={\delta\gamma_{0}}\cdot{1\over 1+\delta}\cdot{1\over 1-{1\over 1+\delta}}\leq\gamma_{0} . 3.3.4 OPT(\tilde{I}) Approximates OPT(I) In this subsection, we show that total processing time of the jobs from the intervals excluded from \tilde{I} is small, and that OPT(\tilde{I}) approximates OPT(I) . Let I^{\prime} be the instance corresponding to \tilde{I} , that is, \langle n_{k},\tilde{p}_{k}\rangle\in I^{\prime} iff \langle\tilde{n}_{k},\tilde{p}_{k}\rangle\in\tilde{I} . Note that the difference between I^{\prime} and \tilde{I} lies in the number of jobs only. With the Lemmas 15 and 17 , we can use a similar argument as in the proof of Lemma 9 to show that, with probability at least (1-3\gamma_{0}) , (1-2{c}m\delta)OPT(I^{\prime})\leq OPT(\tilde{I})\leq(1+6{c}m\delta)OPT(I^{\prime})\kern 5.0pt, (11) where {c}=4 and \delta\leq\tfrac{1}{4c} . Compared with instance I , the instance I^{\prime} excludes jobs from intervals not in H and rounds up the processing times of the jobs from intervals in H . In the following, we give an upper bound on the total processing time of those jobs that belong to intervals not in H . Lemma 18 With probability at least (1-3\gamma_{0}) , the total processing time of the jobs in the intervals I_{k} , I_{k}\not\in H , is at most 4\delta OPT(I) . Proof: There are three types of intervals that are not included in H . Consequently there are three types of jobs not considered in the estimated sketch instance \tilde{I} . The first type of jobs consists of those whose processing time is greater than w_{0} . By Lemma 10 , with probability at most \gamma_{0} , the total processing time of these jobs exceeds {\delta}OPT(I) . The second type of jobs includes those whose processing time is very small; specifically, their processing times belong to intervals I_{k} with k>h . We show that, with probability at most \gamma_{0} , the total processing time of these jobs is more than {\delta}OPT(I) . Let h_{2} be the largest index of the intervals such that (\sum_{j\in I_{t},t>h_{2}}p_{j})>{\delta P\over m} . By Chernoff bound (with \alpha=\frac{1}{2} ), with probability at most e^{-\frac{1}{2}(\frac{1}{2})^{2}(\frac{\delta}{m})K}\leq e^{-\frac{1}{8}\frac{\delta K}{m}}=e^{-\frac{d_{0}}{8}}\leq\gamma_{0}\kern 5.0pt, we have (\sum_{t>h_{2}}X_{t})\leq\frac{\delta{K}}{2m} . By the definition of h in Step 2. 2.a. of Adaptive-Sketch-Algorithm, we have \sum_{k>h}X_{k}\leq\frac{\delta{K}}{4m} . That is, the probability that (\sum_{j\in I_{k},k>h}p_{j}) is greater than \frac{\delta P}{m} (and thus {\delta}OPT(I) ) is at most \gamma_{0} . Finally, the last type of jobs not included in H are those whose processing time belongs to an interval I_{k} , where 1,1\leq k\leq h\} , and show that (1-2\delta)OPT(I)\leq OPT(\tilde{I})\leq(1+\delta)OPT(I) . In particular, we can easily show that it is an (\alpha,\beta_{1},\beta_{2}) -sketch, where \alpha=1 , \beta_{1}=2\delta=\tfrac{\epsilon}{4} , and \beta_{2}=2\delta=\tfrac{\epsilon}{4} . Thus, we have the following lemma. Lemma 20 There is a O(n) time algorithm such that given an instance I and \epsilon\in(0,1) , it outputs an (\alpha,\beta_{1},\beta_{2}) -sketch, \tilde{I}=\{,1\leq k\leq h\} where \alpha=1 , \beta_{1}=\beta_{2}=\tfrac{\epsilon}{4} , and h=O(\tfrac{1}{\epsilon}\log{\tfrac{n}{\epsilon})} . Once we get the input sketch, we can either apply the Meta-Algorithm to get an approximation or use the Modified Meta-Algorithm to get a sketch schedule which then can be converted to a real schedule. Theorem 10 Assume that there is a (1+\alpha) -approximation algorithm A for the makespan problem of n jobs on m machines, with running time A(n,m,\alpha) . Then for any \epsilon\in(0,1) , there is a O(A(h(m,\delta),m,\delta)+n) time (1+\epsilon) -approximation scheme for an input of n jobs, where \delta={\epsilon\over 3} , and h(m,\delta)=\left\lceil m\over\delta\right\rceil . A schedule can be obtained in additional O(\tfrac{1}{\epsilon}\log\tfrac{n}{\epsilon}+m) time. Note that, from the theorem, whenever A(\tfrac{3m}{\epsilon},m,\tfrac{m}{\epsilon})=O(n) , we have an approximation scheme that runs in linear time. For example, for the algorithm in [ 22 ] , A(\tfrac{3m}{\epsilon},m,\tfrac{m}{\epsilon})=2^{O(\tfrac{1}{\epsilon}(\log{1\over\epsilon})^{4})}+\tfrac{m}{\epsilon}(\log\tfrac{m}{\epsilon}) which is O(n) when m=o(n) . Consequently, by invoking the algorithm of [ 22 ] only on a subset of jobs in the sketch instance, we obtain a deterministic approximation scheme with overall running time O(n) . This is asymptotically faster than applying the algorithm of [ 22 ] directly to the entire instance. 5 Conclusions In this paper, we designed the sublinear time algorithms for the classical parallel machine makespan minimization scheduling problem. Using proportional weighted random sampling, our algorithms return an approximate value for the optimal makespan in sublinear time. These algorithms will help manufactures and service industry to make fast decision on production planning as well as accepting/rejecting orders. Furthermore, our algorithms can generate a sketch schedule which, if needed, can be used to produce a real schedule when the complete job information is obtained. It is worth noting that weighted random sampling is well-suited for many scheduling problems with arbitrary job processing times. We believe our approach can be extended to other scheduling problems as well.