Open Research Index

Graham's bounds for list scheduling and LPT on identical machines: 2 − 1/m, 4/3 − 1/(3m) and their tight instances

JD Jones

Palomar Registrypalomar/PALOMAR-2026-10-18-000021Oct 18, 2026cs.DSscore 0

A Lean 4 development of Graham's two bounds for scheduling independent jobs on identical machines to minimize the makespan (R. L. Graham, Bounds for certain multiprocessing anomalies, Bell System Tech. J. 45 (1966) 1563-1581; Bounds on multiprocessing timing anomalies, SIAM J. Appl. Math. 17 (1969) 416-429; both restated with their examples in his survey Bounds on multiprocessing anomalies and related packing algorithms, AFIPS Spring Joint Computer Conference (1972) 205-217). n jobs of nonnegative real lengths p : Fin n -> R are run without interruption on m >= 1 identical machines; an…

SourceRepositoryJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/palomar/PALOMAR-2026-10-18-000021
curl -X POST /api/v1/records/palomar/PALOMAR-2026-10-18-000021/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-10-18-000021/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'