Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.04059 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915974862602240 |
|---|---|
| author | Fu, Bin Huo, Yumei Zhao, Hairong |
| author_facet | Fu, Bin Huo, Yumei Zhao, Hairong |
| contents | We consider the classical makespan minimization scheduling problem where $n$ jobs must be scheduled on $m$ identical machines. Using weighted random sampling, we developed two sublinear time approximation schemes: one for the case where $n$ is known and the other for the case where $n$ is unknown. Both algorithms not only give a $(1+3ε)$-approximation to the optimal makespan but also generate a sketch schedule.
Our first algorithm, which targets the case where $n$ is known and draws samples in a single round under weighted random sampling, has a running time of $\tilde{O}(\tfrac{m^5}{ε^4} \sqrt{n}+A(\ceiling{m\over ε}, ε ))$, where
$A(\mathcal{N}, α)$ is the time complexity of any $(1+α)$-approximation scheme for the makespan minimization of $\mathcal{N}$ jobs.
The second algorithm addresses the case where $n$ is unknown. It uses adaptive weighted random sampling, %\textit{that is}, it draws samples in several rounds, adjusting the number of samples after each round,
and runs in sublinear time $\tilde{O}\left( \tfrac{m^5} {ε^4} \sqrt{n} +
A(\ceiling{m\over ε}, ε )\right)$. We also provide an implementation that generates a weighted random sample using $O(\log n)$ uniform random samples. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_04059 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Minimizing Makespan in Sublinear Time via Weighted Random Sampling Fu, Bin Huo, Yumei Zhao, Hairong Data Structures and Algorithms We consider the classical makespan minimization scheduling problem where $n$ jobs must be scheduled on $m$ identical machines. Using weighted random sampling, we developed two sublinear time approximation schemes: one for the case where $n$ is known and the other for the case where $n$ is unknown. Both algorithms not only give a $(1+3ε)$-approximation to the optimal makespan but also generate a sketch schedule. Our first algorithm, which targets the case where $n$ is known and draws samples in a single round under weighted random sampling, has a running time of $\tilde{O}(\tfrac{m^5}{ε^4} \sqrt{n}+A(\ceiling{m\over ε}, ε ))$, where $A(\mathcal{N}, α)$ is the time complexity of any $(1+α)$-approximation scheme for the makespan minimization of $\mathcal{N}$ jobs. The second algorithm addresses the case where $n$ is unknown. It uses adaptive weighted random sampling, %\textit{that is}, it draws samples in several rounds, adjusting the number of samples after each round, and runs in sublinear time $\tilde{O}\left( \tfrac{m^5} {ε^4} \sqrt{n} + A(\ceiling{m\over ε}, ε )\right)$. We also provide an implementation that generates a weighted random sample using $O(\log n)$ uniform random samples. |
| title | Minimizing Makespan in Sublinear Time via Weighted Random Sampling |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.04059 |