{
  "$type": "site.standard.document",
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.04059v1",
  "publishedAt": "2026-02-05T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Bin Fu",
    "Yumei Huo",
    "Hairong Zhao"
  ],
  "textContent": "**Authors:** Bin Fu, Yumei Huo, Hairong Zhao\n\nWe 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"
}