Pith. sign in

REVIEW 1 major objections 6 minor 40 references

Faster Exponential Algorithms for Multi-Machine Scheduling Problems

T0 review · 1 major / 6 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that weighted completion-time scheduling can be solved in $O(2.755^n)$ time and weighted tardy-job scheduling in $O^*(2^n)$ time, and that, assuming the Asymptotic Rank Conjecture, Bin Packing can be solved in…

desk verdict The scheduling results are solid and genuinely new; the conditional bin-packing theorem is clever but rests on an unproved no-false-positives claim that must be fixed before the result can be trusted as stated. read the letter →

arxiv 2608.12224 v1 pith:DGLPOK2Q submitted 2026-08-12 cs.DS

Anubhav Dhar , Anita Dürr , Ahmed Ghazy , Jakob Greilhuber , Karol Węgrzycki This is my paper · ORCID
classification cs.DS MSC 68Q2568W4090B35
keywords schedulingexactexponential-timealgorithmsmulti-machineweightedcompletiontimetardyjobsbinpackingasymptoticrankconjecturemeet-in-the-middle
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper is about the exact exponential-time complexity of two fundamental multi-machine scheduling problems and of their common relative, Bin Packing. Its central claim is that $P\mid\mid \sum w_j C_j$ can be solved in $O(2.755^n)$ and $P\mid\mid \sum w_j U_j$ in $O^*(2^n)$, improving the previous $O^*(3^n)$ algorithms. It further claims that, assuming the Asymptotic Rank Conjecture, Bin Packing can be solved in $O((2-\varepsilon)^n)$ for some constant $\varepsilon>0$, breaking the classic $O^*(2^n)$ barrier. A reader should care because these are benchmark NP-hard problems: each improvement in the base of the exponential is a step toward understanding how hard exact optimization on identical machines really is, and the Bin Packing result conditionally settles a long-standing open question. The methods are combinations of meet-in-the-middle, linear-programming query data structures, fast subset convolution, and a cardinality-based case analysis.

What carries the argument

The load-bearing identity is the recurrence of Lemma 10: for any split of $i$ machines into $j$ and $i-j$, the optimum $\mathrm{OPT}(i,S)$ equals $\min_{S'\subseteq S,\, |S'|\le j|S|/i}\{\mathrm{OPT}(j,S')+\mathrm{OPT}(i-j,S\setminus S')\}$, because in an optimal schedule the $j$ machines with the fewest jobs contain at most $j|S|/i$ jobs. This turns the naive $3^n$ enumeration of subsets into enumeration over subsets of size at most a constant fraction, whose count is bounded by $2^{H(\alpha)n}$; the base cases for $m\le 3$ are handled by a meet-in-the-middle scheme that encodes each half-partition as a point and answers the min-over-partitions query with a 2- or 3-dimensional linear-programming data structure. For $P\mid\mid \sum w_j U_j$, the same recurrence is evaluated with Min-Plus Subset Convolution, and the single-machine base case is the polynomial-time algorithm of [32]. For Bin Packing, the machinery is the four-case cardinality split together with a subset-sum DP table $\mathrm{BP}[i,S]$ and, in Case D, a reduction to $3$-way Partitioning for $(1-\varepsilon)/2$-bounded set families, solved under ARC.

What would settle it

For all Bin Packing instances with up to 20 items and between 7 and 10 bins, run the four-case algorithm and an exact $O^*(2^n)$ dynamic program; if the four-case procedure says Yes on any instance where the exact DP says No, then the no-false-positives claim behind Lemma 6 is false and Theorem 4's soundness collapses. A faster preliminary check is to run the Lemma 6 subroutine alone on all six-bin subinstances generated during Case B and compare its answers with exact packing.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is a pair of exact algorithms and one conditional algorithm. Theorem 1 gives $O(2.755^n)$ for minimizing total weighted completion time on identical parallel machines; Theorem 2 gives $O^*(2^n)$ for the weighted number of tardy jobs; Theorem 3 refines the completion-time bound for fixed small machine counts; Theorem 4 states that under the Asymptotic Rank Conjecture there is a constant $\varepsilon>0$ for which Bin Packing on $n$ items can be decided with high probability in $O((2-\varepsilon)^n)$ time. The scheduling algorithms use a dynamic program whose transition only needs to split off a subset of size at most a fixed fraction of the current job set, with base cases for two and three machines accelerated by meet-in-the-middle and a data structure for linear programming queries; the tardy-jobs algorithm uses fast subset convolution over the DP transitions. The Bin Packing algorithm partitions all possible solutions into four cases according to how many items lie in the largest bins, and solves each case by subset-sum DP, the constant-bin algorithm, random sampling, or a reduction to 3-way Partitioning, the last being the only ARC-dependent ingredient.

Load-bearing premise

The Bin Packing result depends on the fixed-bin subroutine never saying Yes on an unpackable instance, a property that the cited theorem does not state and that the paper asserts as "indeed the case."

Editorial extensions

If this is right

  • For $P\mid\mid \sum w_j C_j$, the previous $O^*(3^n)$ bound improves to $O(2.755^n)$, giving the first known algorithm with base below 3 for this problem.
  • For $P\mid\mid \sum w_j U_j$, the bound improves to $O^*(2^n)$, matching the classic inclusion-exclusion bound for Bin Packing.
  • For fixed machine counts, the constant-base bounds improve further: $O^*(m^{n/2})$ for $m\le 3$, and $O(2.389^n)$, $O(2.726^n)$, $O(2.733^n)$ for $m=4,5,6$.
  • Assuming ARC, Bin Packing admits a randomized $O((2-\varepsilon)^n)$-time decision procedure, conditionally resolving an open question.
  • A SETH-based lower bound ruling out $O^*((2-\varepsilon)^n)$ Bin Packing would imply that SETH and ARC are not both true, so the result forms a barrier against such a lower bound.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The no-false-positives premise behind Lemma 22 is testable in isolation: the six-bin subroutine could be compared against exact DP on small random instances, and any violation would require a different constant-bin subroutine for Theorem 4.
  • The four-case cardinality split is a template that likely transfers to other packing and scheduling problems: classify feasible solutions by how items distribute across bins, then attack each class with the cheapest available sub-$2^n$ oracle.
  • The unbalanced split $\alpha\approx0.628$ for $m=4$ illustrates that when preprocessing and query costs are asymmetric, the optimal meet-in-the-middle split is not half-half; similar trade-off analysis could improve other LP-query-based DPs.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 6 minor

Summary. The paper gives exact exponential algorithms for two multi-machine scheduling problems and a conditional algorithm for Bin Packing. It claims P||Σw_jC_j can be solved in O(2.755^n) time, with further improvements O(2.389^n), O(2.726^n), and O(2.733^n) for 4, 5, and 6 machines, and P||Σw_jU_j in O*(2^n) time. The scheduling algorithms use dynamic programming whose base cases are solved by meet-in-the-middle with a linear-programming-query data structure (for weighted completion time) and by Fast Subset Convolution plus Moore's algorithm (for tardy jobs). The Bin Packing section, under the Asymptotic Rank Conjecture, claims an O((2−ε)^n) decision procedure based on a four-case analysis that combines a fixed-constant-bin packing subroutine and a 3-way Partitioning subroutine.

Significance. The scheduling results are clear algorithmic improvements over the O*(3^n) baseline, and the proofs appear technically sound; the recurrences, entropy bounds, and case analyses are written out in detail. Theorem 3's fixed-machine bounds are additional useful contributions. The Bin Packing result, if fully supported, would be a substantial advance under ARC, and the paper clearly labels the ARC assumption. However, I cannot endorse Theorem 4 as written because the claimed no-false-positives property of the cited constant-bin algorithm is load-bearing and unproved; this is a correctness gap, not a presentation issue. The scheduling sections are independent of the Bin Packing section and appear publishable on their own.

major comments (1)
  1. [Section 6, Lemma 6] The assertion that the algorithm of [35, Theorem 1.1] 'has no false positives' is load-bearing and currently unsupported. The manuscript itself notes that the cited theorem does not state this property, and no proof or certificate argument is supplied. Lemma 22 uses this property to conclude that the Case B test never accepts an infeasible instance: the test accepts only if for some X∈W both BP[m−6,X]=0 and the Lemma 6 subroutine reports that I\X packs into 6 bins, and the 'No' direction of Lemma 22 is exactly the contrapositive of that implication. Moreover, Lemma 22 calls the subroutine for all 2^{H(ε)n} members of W, so a per-call false-positive probability of 1/poly(n) would be amplified and cannot be absorbed by a union bound. Theorem 4's final sentence 'none of the four algorithms have false positives' inherits this gap. I recommend proving the no-false-positives property directly from [35], or replacing the subroutine with one that returns a verifiable packing, or with an algorithm whose false-positive probability is exponentially small and explicitly accounted for in the analysis.
minor comments (6)
  1. [Lemma 20] The statement says the table entries are returned for i∈[m], but Lemma 23 (and the m=6 case of Lemma 22) needs BP[0,·]; the proof initializes the i=0 row, so the statement should read i∈{0}∪[m].
  2. [Lemma 22 and Theorem 4] The constant from Lemma 6 is typeset as 'ε6' and sometimes as 'ε^6'; use ε_6 to avoid confusion with the small constant ε.
  3. [Lemma 23] The number of sampled sets, 2^{(1−ε)n}n^2, may not be an integer; state that a ceiling or rounding is used. This does not affect the high-probability claim.
  4. [Section 6, solution reconstruction] In the discussion of reconstructing a packing from a decision oracle, the trivial case 'm=n' should read 'm≥n', since m>n items can also be placed in distinct bins.
  5. [Lemma 24] In the correctness proof, 'we found S1,S2,S3' should be phrased in terms of existence, since Lemma 7 is stated as a decision procedure; a standard self-reduction can supply witnesses if construction is needed.
  6. [Theorem 4] Lemma 23 is stated with success probability only 1/2; the proof of Theorem 4 should say explicitly that this is boosted to 1−n^{−Ω(1)} before the four algorithms are combined.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the algorithms are standard dynamic-programming and meet-in-the-middle reductions with independent external primitives; the sole flagged issue is an unsupported no-false-positives assertion, which is a correctness risk rather than a circular step.

full rationale

The central claims are derived by genuine reductions, not by definitional equivalence. Theorem 1 uses the DP recurrence of Lemma 10, justified by an optimal-schedule argument, together with Lemma 13's meet-in-the-middle scheme and the external LP-query data structure of Guibas et al.; the constants such as alpha=0.628 are selected by optimizing the entropy bound, not fitted to the claimed running time. Theorem 2 is the standard subset-convolution DP using Moore's algorithm and Björklund et al.'s Fast Subset Convolution as independent ingredients. Theorem 4 reduces Bin Packing to four cases; each of Lemmas 21, 22, 23, and 24 constructs an explicit packing from any Yes answer, so no case output is presupposed by its input. The external black boxes [35] and [2] are cited published results whose assumptions do not include the target theorem, and the ARC dependence is explicit and conditional. The only load-bearing statement that goes beyond the cited support appears after Lemma 6: 'Note that [35, Theorem 1.1] does not state that the algorithm has no false positives, but this is indeed the case.' This is a missing-support and correctness risk for the No-side of Theorem 4, but it is not circularity: the property is asserted, not derived from the target result, and no prediction is equivalent by construction to a fitted parameter or to a self-citation chain. Self-citation of [35] (Węgrzycki is a co-author) is normal reuse of a published SICOMP result and does not make the derivation circular. Accordingly, the circularity score is 0.

Assumptions & free parameters 2 free parameters · 8 assumptions · 0 invented entities

The central claims are built from known algorithmic components plus one conditional conjecture. The only hand-chosen quantities are algorithmic split constants; there is no data fitting or hidden normalization. The main self-cited ingredients, Lemma 6 and Lemma 8, come from a published SICOMP paper coauthored by one of the present authors; they are used as black boxes, and the added no-false-positives assertion is the one unverified step.

free parameters (2)
  • alpha (Lemma 14 split fraction) = 0.628
    Hand-chosen to balance the two exponential terms 1.7548^{αn} and 4^{(1-α)n} in the m=4 algorithm; it is an optimization parameter, not fitted to empirical data.
  • epsilon (Bin Packing case analysis) = Any sufficiently small rational constant with ε ≤ 1/100 and H(ε) < ε6
    Chosen by hand to satisfy the entropy and constant constraints; it exists and is not numerically specified. It affects the constants in Lemmas 21-24, not the truth of the result.
assumptions (8)
  • standard math Entropy bound for binomial coefficients: (n choose αn) ≤ 2^{H(α)n}
    Used throughout the running time analyses in Sections 3-6.
  • standard math Smith's rule: on one machine, jobs are optimally scheduled by nondecreasing p_j/w_j
    Used in Lemmas 11-14 for the weighted completion time problem.
  • domain assumption Moore's algorithm solves P1||ΣUj in polynomial time
    Used to initialize DP[1,S] in Theorem 2; a standard scheduling result.
  • standard math Fast subset convolution computes min-plus subset convolution in O*(2^n)
    Lemma 17, used for the transitions in Theorem 2.
  • standard math Guibas et al. data structure supports 2/3-dimensional linear programming queries in O(log n) after O(n log n) preprocessing
    Lemma 5, central to Lemmas 13 and 14.
  • ad hoc to paper Asymptotic Rank Conjecture (ARC)
    Assumed for Theorem 4 and Lemma 7; it is a named conjecture, not a derived fact.
  • ad hoc to paper Nederlof et al. fixed-bin packing algorithm has no false positives
    Stated without proof in Section 6 although the cited theorem does not state it; needed for the No-correctness of Case B.
  • standard math Nederlof et al. combinatorial bound (Lemma 8) and Björklund et al. 3-way Partitioning bound (Lemma 7)
    Cited black-box results used in Cases C and D of the Bin Packing algorithm.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Faster Exponential Algorithms for Multi-Machine Scheduling Problems." pith.science (2026). https://pith.science/paper/DGLPOK2Q

@misc{pith2026260812224,
  author       = {Pith},
  title        = {Pith review of: Faster Exponential Algorithms for Multi-Machine Scheduling Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DGLPOK2Q}},
  note         = {Machine review of arXiv:2608.12224}
}
abstract

Minimizing the weighted completion times ($P \mid \mid \Sigma w_j C_j$) and weighted number of tardy jobs ($P \mid \mid \Sigma w_j U_j$) on multiple identical machines are two classical NP-hard scheduling problems. As shown by Lent\'e et al. (2014), both problems can be solved in time ${O}^{\star}(3^n)$. In this paper, we improve these bounds to ${O}(2.755^n)$ and ${O}^{\star}(2^n)$, respectively. Our algorithm for $P \mid \mid \Sigma w_j C_j$ exploits the meet-in-the-middle paradigm and an efficient data structure answering linear programming queries. Additionally, when the number of machines is at most $6$, we show that the running time for $P \mid \mid \Sigma w_j C_j$ can further be improved. Both scheduling problems are generalizations of the classical Bin Packing problem, which can be solved in ${O}^{\star}(2^n)$ time. Improving this running time is an important open question. We show that, when assuming the Asymptotic Rank Conjecture (ARC), Bin Packing can be solved in time ${O}((2-\varepsilon)^n)$ for some $\varepsilon >0$. Our algorithm makes use of two main ingredients: the recent ${O}((2-\varepsilon)^n)$-time algorithm of Nederlof et al. [SICOMP'23] for Bin Packing when the number of bins is a fixed constant, and the ${O}((2-\varepsilon)^n)$-time algorithm of Bj\"orklund et al. [SODA'25] for special instances of the $3$-way Partitioning problem when assuming ARC.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 19 canonical work pages

  1. [35]

    Jesper Nederlof, Jakub Pawlewicz, C \' e line M. F. Swennenhuis, and Karol W e grzycki. A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics . SIAM J. Comput. , 52(6):1369--1412, 2023. https://doi.org/10.1137/22M1478112 doi:10.1137/22M1478112

    doi:10.1137/22m1478112 2023

  2. [21]

    Faster minimization of total weighted completion time on parallel machines

    Danny Hermelin, Tomohiro Koana, and Dvir Shabtay. Faster minimization of total weighted completion time on parallel machines. CoRR , abs/2502.13631, 2025. https://arxiv.org/abs/2502.13631 arXiv:2502.13631 , https://doi.org/10.48550/ARXIV.2502.13631 doi:10.48550/ARXIV.2502.13631

    arXiv doi:10.48550/arxiv.2502.13631 2025

  3. [1]

    Scheduling lower bounds via AND subset sum

    Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay. Scheduling lower bounds via AND subset sum. J. Comput. Syst. Sci. , 127:29--40, 2022. https://doi.org/10.1016/J.JCSS.2022.01.005 doi:10.1016/J.JCSS.2022.01.005

    work page doi:10.1016/j.jcss.2022.01.005 2022

  4. [2]

    Fast deterministic chromatic number under the asymptotic rank conjecture

    Andreas Bj \" o rklund, Radu Curticapean, Thore Husfeldt, Petteri Kaski, and Kevin Pratt. Fast deterministic chromatic number under the asymptotic rank conjecture. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025 , pages 2804--2818....

    doi:10.1137/1.9781611978322.91 2025

  5. [3]

    o rklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets M \

    Andreas Bj \" o rklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets M \" o bius: fast subset convolution . In David S. Johnson and Uriel Feige, editors, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007 , pages 67--74. ACM , 2007. https://doi.org/10.1145/1250790.1250801 d...

    arXiv 2007

  6. [4]

    Set partitioning via inclusion-exclusion

    Andreas Bj \" o rklund, Thore Husfeldt, and Mikko Koivisto. Set partitioning via inclusion-exclusion. SIAM J. Comput. , 39(2):546--563, 2009. https://doi.org/10.1137/070683933 doi:10.1137/070683933

    doi:10.1137/070683933 2009

  7. [5]

    The asymptotic rank conjecture and the set cover conjecture are not both true

    Andreas Bj \" o rklund and Petteri Kaski. The asymptotic rank conjecture and the set cover conjecture are not both true. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024 , pages 859--870. ACM , 2024. https://doi.org/10.1145/361...

    arXiv 2024

  8. [6]

    Kronecker Scaling of Tensors with Applications to Arithmetic Circuits and Algorithms

    Andreas Bj\" o rklund, Petteri Kaski, Tomohiro Koana, and Jesper Nederlof. Kronecker Scaling of Tensors with Applications to Arithmetic Circuits and Algorithms . In Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis, editors, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) , volume 374 of Leibni...

    work page 2026

Show all 40 references
  1. [7]

    Faster convolutions: Yates and strassen revisited

    Cornelius Brand, Radu Curticapean, Baitian Li, and Kevin Pratt. Faster convolutions: Yates and strassen revisited. In Sepehr Assadi and Eva Rotenberg, editors, 2026 Symposium on Simplicity in Algorithms, SOSA 2026, Vancouver, BC, Canada, January 12-14, 2026 , pages 328--339. S...

    2026 doi

  2. [8]

    Tight (S)ETH-Based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-machine Scheduling

    Karl Bringmann, Anita D \" u rr, and Karol W e grzycki. Tight (S)ETH-Based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-machine Scheduling . In Aditya Bhaskara and Artur Czumaj, editors, Proceedings of the 58th Annual ACM Symposium on Theory of Comput...

    2026

  3. [9]

    Faster minimization of tardy processing time on a single machine

    Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, and Philip Wellnitz. Faster minimization of tardy processing time on a single machine. Algorithmica , 84(5):1341--1356, 2022. https://doi.org/10.1007/S00453-022-00928-W doi:10.1007/S00453-022-00928-W

    2022 doi

  4. [10]

    Bruno, Edward G

    John L. Bruno, Edward G. Coffman Jr., and Ravi Sethi. Scheduling independent tasks to reduce mean finishing time. Commun. ACM , 17(7):382--387, 1974. https://doi.org/10.1145/361011.361064 doi:10.1145/361011.361064

    1974

  5. [11]

    Timothy M. Chan. Fixed-dimensional linear programming queries made easy. In Sue Whitesides, editor, Proceedings of the Twelfth Annual Symposium on Computational Geometry, Philadelphia, PA, USA, May 24-26, 1996 , pages 284--290. ACM , 1996. https://doi.org/10.1145/237218.237397...

    1996

  6. [12]

    Timothy M. Chan. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discret. Comput. Geom. , 16(4):361--368, 1996. https://doi.org/10.1007/BF02712873 doi:10.1007/BF02712873

    1996 doi

  7. [13]

    Cover and Joy A

    Thomas M. Cover and Joy A. Thomas. Elements of information theory ( 2. ed.) . Wiley, 2006. https://doi.org/10.1002/047174882X doi:10.1002/047174882X

    2006 doi

  8. [14]

    Jianzhong Du and Joseph Y. - T. Leung. Minimizing total tardiness on one machine is NP -hard. Math. Oper. Res. , 15(3):483--495, 1990. https://doi.org/10.1287/MOOR.15.3.483 doi:10.1287/MOOR.15.3.483

    1990 doi

  9. [15]

    Faster Algorithms for k-Orthogonal Vectors in Low Dimension

    Anita D \" u rr, Evangelos Kipouridis, Michael Lampis, and Karol W e grzycki. Faster Algorithms for k-Orthogonal Vectors in Low Dimension . In 53rd International Colloquium on Automata, Languages, and Programming, ICALP 2026, Royal Holloway, University of London, Egham, United...

    2026 doi

  10. [16]

    Minimizing tardy processing time on a single machine in near-linear time

    Nick Fischer and Leo Wennmann. Minimizing tardy processing time on a single machine in near-linear time. TheoretiCS , 4, 2025. https://doi.org/10.46298/THEORETICS.25.14 doi:10.46298/THEORETICS.25.14

    2025 doi

  11. [17]

    Fast approximation algorithm for job sequencing with deadlines

    George Gens and Eugene Levner. Fast approximation algorithm for job sequencing with deadlines. Discret. Appl. Math. , 3(4):313--318, 1981. https://doi.org/10.1016/0166-218X(81)90008-1 doi:10.1016/0166-218X(81)90008-1

    1981 doi

  12. [18]

    Graham, Eugene L

    Ronald L. Graham, Eugene L. Lawler, Jan Karel Lenstra, and Alexander H.G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics , 5(2):287--326, 1979. https://doi.org/10.1016/S0167-5060(08)70356-X doi:1...

    1979 doi

  13. [19]

    Guibas, Jorge Stolfi, and Kenneth L

    Leonidas J. Guibas, Jorge Stolfi, and Kenneth L. Clarkson. Solving related two-and three-dimensional linear programming problems in logarithmic time. Theor. Comput. Sci. , 49:81--84, 1987. https://doi.org/10.1016/0304-3975(87)90101-0 doi:10.1016/0304-3975(87)90101-0

    1987 doi

  14. [20]

    Minimizing the Weighted Number of Tardy Jobs Is W[1]-Hard

    Klaus Heeger and Danny Hermelin. Minimizing the Weighted Number of Tardy Jobs Is W[1]-Hard . In Timothy M. Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors, 32nd Annual European Symposium on Algorithms, ESA 2024, Royal Holloway, London, United Kingdom, Septemb...

    2024 doi

  15. [22]

    Minimizing the weighted number of tardy jobs via (max,+)-convolutions

    Danny Hermelin, Hendrik Molter, and Dvir Shabtay. Minimizing the weighted number of tardy jobs via (max,+)-convolutions. INFORMS J. Comput. , 36(3):836--848, 2024. https://doi.org/10.1287/IJOC.2022.0307 doi:10.1287/IJOC.2022.0307

    2024

  16. [23]

    Bounding the running time of algorithms for scheduling and packing problems

    Klaus Jansen, Felix Land, and Kati Land. Bounding the running time of algorithms for scheduling and packing problems. SIAM J. Discret. Math. , 30(1):343--366, 2016. https://doi.org/10.1137/140952636 doi:10.1137/140952636

    2016 doi

  17. [24]

    Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New Yo...

    1972 doi

  18. [25]

    On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs

    Kim - Manuel Klein, Adam Polak, and Lars Rohwedder. On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs . In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023...

    2023 doi

  19. [26]

    Scheduling meets n-fold integer programming

    Dusan Knop and Martin Kouteck \' y . Scheduling meets n-fold integer programming. J. Sched. , 21(5):493--503, 2018. https://doi.org/10.1007/S10951-017-0550-0 doi:10.1007/S10951-017-0550-0

    2018 doi

  20. [27]

    Lawler, Jan Karel Lenstra, Alexander H

    Eugene L. Lawler, Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, and David B. Shmoys. Chapter 9 Sequencing and scheduling: Algorithms and complexity . In Stephen C. Graves, Alexander H. G. Rinnooy Kan, and Paul Herbert Zipkin, editors, Logistics of Production and Inventory , ...

    1993 doi

  21. [28]

    Lawler and J

    Eugene L. Lawler and J. Michael Moore. A functional equation and its application to resource allocation and sequencing problems. Management Science , 16(1):77--84, 1969. https://doi.org/10.1287/mnsc.16.1.77 doi:10.1287/mnsc.16.1.77

    1969 doi

  22. [29]

    Lenstra, A.H.G

    J.K. Lenstra, A.H.G. Rinnooy Kan , and P. Brucker. Complexity of machine scheduling problems. In P.L. Hammer, E.L. Johnson, B.H. Korte, and G.L. Nemhauser, editors, Studies in Integer Programming , volume 1 of Annals of Discrete Mathematics , pages 343--362. Elsevier, 1977. ht...

    1977 doi

  23. [30]

    Exponential algorithms for scheduling problems

    Christophe Lent \'e , Mathieu Liedloff, Ameur Soukhal, and Vincent T'kindt. Exponential algorithms for scheduling problems . Technical report, Ecole Polytechnique de l’Université de Tours, 2014. URL: https://hal.science/hal-00944382v1

    2014

  24. [31]

    William L. Maxwell. On sequencing n jobs on one machine to minimize the number of late jobs. Management Science , 16(5):295--297, 1970. https://doi.org/10.1287/mnsc.16.5.295 doi:10.1287/mnsc.16.5.295

    1970 doi

  25. [32]

    Michael Moore

    J. Michael Moore. An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science , 15(1):102--109, 1968. https://doi.org/10.1287/mnsc.15.1.102 doi:10.1287/mnsc.15.1.102

    1968 doi

  26. [33]

    Finding large set covers faster via the representation method

    Jesper Nederlof. Finding large set covers faster via the representation method. In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, Aarhus, Denmark, August 22-24, 2016 , volume 57 of LIPIcs , pages 69:1--69:15. Schlos...

    2016 doi

  27. [34]

    Fine-grained complexity of NP -complete problems

    Jesper Nederlof. An invitation to "Fine-grained complexity of NP -complete problems" . Comput. Sci. Rev. , 61:100919, 2026. https://doi.org/10.1016/J.COSREV.2026.100919 doi:10.1016/J.COSREV.2026.100919

    2026

  28. [36]

    F. P. Preparata and S. J. Hong. Convex hulls of finite sets of points in two and three dimensions. Commun. ACM , 20(2):87–93, February 1977. https://doi.org/10.1145/359423.359430 doi:10.1145/359423.359430

    1977

  29. [37]

    Preparata and David E

    Franco P. Preparata and David E. Muller. Finding the intersection of n half-spaces in time O(n log n) . Theor. Comput. Sci. , 8:45--55, 1979. https://doi.org/10.1016/0304-3975(79)90055-0 doi:10.1016/0304-3975(79)90055-0

    1979 doi

  30. [38]

    Rothkopf

    Michael H. Rothkopf. Scheduling independent tasks on parallel processors. Management Science , 12(5):437--447, 1966. https://doi.org/10.1287/mnsc.12.5.437 doi:10.1287/mnsc.12.5.437

    1966 doi

  31. [39]

    Algorithms for scheduling independent tasks

    Sartaj Sahni. Algorithms for scheduling independent tasks. J. ACM , 23(1):116--127, 1976. https://doi.org/10.1145/321921.321934 doi:10.1145/321921.321934

    1976

  32. [40]

    Wayne E. Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterly , 3(1-2):59--66, 1956. https://doi.org/10.1002/nav.3800030106 doi:10.1002/nav.3800030106

    1956 doi

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.