Pith. sign in

REVIEW 3 major objections 4 minor 66 references

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling

T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read This paper proves that the precedence-constrained resource scheduling problem—jobs that draw on a shared resource while respecting dependency order—has no polynomial-time o((log t_max)^alpha)-factor approximation unless P=NP, no o((log n)^a

desk verdict The chains toolbox is broken: Property 2.3 is false, the t_max hardness claim is vacuous, and the online lower bound and reductions collapse; only the positive online algorithm is salvageable. read the letter →

arxiv 2509.01086 v1 pith:B3SBDUSH submitted 2025-09-01 cs.DS

Rathish Das , Hao Sun This is my paper
classification cs.DS MSC 68Q1768W2568W2790B35
keywords precedence-constrainedresourceschedulinghardnessofapproximationonlinecompetitiveratioshortestcommonsupersequencechaingadgetmakespanloading-time
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 takes on a fifty-year-old question: can precedence-constrained resource scheduling—jobs that consume units of a shared resource while respecting dependency order—be approximated in polynomial time within a constant factor? The answer it argues is no: for some constant alpha>0, any o((log t_max)^alpha)-factor approximation is impossible unless P=NP, and any o((log n)^alpha)-factor approximation would put NP in subexponential time. It further shows that an o(log t_max)-approximation would improve the approximation ratio for shortest common super-sequence below the alphabet-size barrier, a long-standing open problem. In the online setting, it proves that no randomized algorithm can beat Omega(log n) or Omega(log t_max) competitive ratio, and it supplies a deterministic algorithm with matching O(min(log n, log t_max))-competitive ratio, plus a term for the number of resource types. The vehicle for all these results is a gadget called a chain, whose defining property is meant to make chains with different skinny-job lengths mutually incompatible.

What carries the argument

The chain gadget: a skinny job of length 2^i (resource use below 1/n, so many can run in parallel) followed by a zero-length fat job consuming the full budget, repeated to make total length 2^m; chains of the same type pack in parallel, while chains of different types are asserted to be incompatible, forcing additive makespan. This incompatibility property is the load-bearing mechanism: it converts scheduling instances into combinatorial objects that can encode LTS partitions and SCS supersequences, and it makes every online algorithm guess which chain blocks the next gadget.

What would settle it

Run two independent chains C(3,1) and C(3,2) in a one-resource instance with budget 1, skinny jobs requiring less than 1/n of the budget, and fat jobs of length 0. If both chains finish in makespan 8 by running all skinny jobs concurrently, Property 2.3's Omega(2^3 + 2^3) bound is refuted, which removes the premise behind the LTS reduction, the SCS reduction, and the Omega(log n) online lower bound.

Watch

Extended reading notes

Core claim

The paper's central claim is that the makespan of precedence-constrained resource scheduling is governed, in the worst case, by the sum of incomparable 'chain' lengths rather than by their maximum. A chain C(m,i) is built from repeated tuples, each a skinny job of processing time 2^i followed by a fat job of length 0 that claims the entire resource; the chain has total length 2^m. The paper asserts that if several chains have pairwise different skinny-job lengths, their fat jobs act as barriers so that the optimum makespan is Omega(2^{m_1}+...+2^{m_p}), even though chains sharing a skinny length pack together at cost max 2^{m_j}. This incompatibility is then used to simulate loading-time sch

Load-bearing premise

The whole lower-bound structure assumes that chains with different skinny-job lengths cannot overlap in time, so p distinct chains cost Omega(sum of their lengths); but the paper defines skinny jobs to use less than 1/n of the resource each and fat jobs to have length 0, so skinny jobs from different chains can actually run concurrently and zero-length fat jobs create no barrier.

Editorial extensions

If this is right

  • If P != NP, the offline problem admits no polynomial-time o((log t_max)^alpha)-approximation, so the known O(log n) upper bound is almost matched in the worst case.
  • Any polynomial-time o((log t_max)^alpha)-approximation algorithm would imply P = NP; any o((log n)^alpha)-approximation would imply NP is contained in DTIME(2^{polylog n}).
  • An o(log t_max)-approximation for scheduling would yield an o(|Sigma|)-approximation for shortest common super-sequence, breaking the alphabet-size barrier that has stood for decades.
  • No randomized online algorithm has competitive ratio o(log n) or o(log t_max), and the paper's deterministic algorithm achieves O(d + min(log n, log t_max)), matching up to constants.
  • With d >= 3 resource types, no online algorithm, randomized or not, can achieve a competitive ratio better than (d-1)/2.

Reading between the lines

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

  • Our inference: the lower-bound proofs require the zero-length fat jobs to act as real barriers between skinny jobs of different lengths; if skinny jobs from different chains are allowed to run concurrently, the claimed Omega(sum of chain lengths) property would fail, and with it the LTS reduction, the SCS reduction, and the online adversary. The paper does not address this edge case.
  • Our inference: a direct test of the central gadget is to simulate two chains C(3,1) and C(3,2) with resource budget 1 and skinny requirement below 1/n: Property 2.3 predicts makespan Omega(16), while a schedule that runs all skinny jobs concurrently would finish both in 8.
  • Our inference: if the chain gadget were repaired by giving fat jobs positive length, the reduction sizes and parameter mapping (t_max = 2^rho, log n = Theta(log t_max)) would need rechecking, since positive-length fat jobs add another multiplicative factor to chain length.
  • Our inference: the SCS connection is one-directional; the paper shows scheduling hardness implies SCS hardness, but not that SCS approximation would improve scheduling, and establishing the converse would require a different gadget.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper studies precedence-constrained resource scheduling with a resource budget, in both offline and online settings. It claims (i) for some constant α>0, no polynomial-time o((log t_max)^α)-factor approximation exists unless P=NP, and similarly no o((log n)^α)-factor approximation unless NP⊂DTIME(2^{polylog n}); (ii) an o(log t_max)-approximation for the scheduling problem would imply an o(|Σ|)-approximation for Shortest Common Supersequence (SCS); (iii) no randomized online algorithm is o(log n)-competitive or o(log t_max)-competitive; and (iv) a deterministic online algorithm with competitive ratio O(d + min{log n, log t_max}). The proofs are built around a new gadget called chains, with an asserted 'incompatibility' property stating that independent chains whose skinny jobs have different powers-of-two lengths cannot be parallelized and force makespan Ω(sum 2^{m_i}).

Significance. The claimed results, if valid, would be significant: they would give the first non-constant hardness of approximation for the offline problem with a fixed number of resource types, a new conditional connection to SCS, and tight bounds for the online problem. The chains toolbox is a natural idea, and the deterministic online algorithm in Section 6 is a useful contribution if its analysis is sound. However, the central incompatibility property is false, and the main t_max hardness theorem is not supported by the reduction as written. These are load-bearing defects in the two headline results of the paper, not presentation issues.

major comments (3)
  1. [§2.1, Property 2.3 (and Appendix A)] Property 2.3 is false as stated. Take two chains C(3,1) and C(3,2). Each chain has total length 8, and its fat jobs have length 0. Because skinny jobs have resource requirement <1/n, the skinny jobs from the two chains can run concurrently; the zero-length fat jobs do not occupy any time. Scheduling the two chains in parallel gives makespan 8, contradicting the claimed Ω(2^3+2^3)=Ω(16). This is not a technicality: the zero-length fat jobs do not act as time barriers. The error is load-bearing in Lemma 5.4, which asserts E[T_Dj]≥(m/4)·2^m because the m/4 completed chains of different types are assumed to require sequential execution. Since chains of different types can in fact run in parallel, the argument yields only a 2^m bound per gadget, and the Ω(log n) and Ω(log t_max) lower bounds of Theorem 5.1 collapse.
  2. [§3.3, proof of Theorem 3.3] The reduction from LTS fixes the number of machines ρ to a constant, as stated immediately before Remark 3.13. Consequently every constructed scheduling instance has t_max ≤ 2^ρ = O(1), independent of n. An o((log t_max)^α)-approximation hypothesis is then an o(1)-factor condition on instances with constant t_max; it cannot be used to contradict the constant-factor LTS hardness of Theorem 3.12. Scaling all skinny lengths by an additional 2^s does not repair the argument: with ρ fixed, ρ^α/4 is a constant while an o((log t_max)^α)=o(s^α) algorithm may have ratio growing like log s and never fall below that constant. Letting ρ grow makes each chain contain 2^{ρ-i}ℓ(m_i) tuples, exponential in ρ, so the reduction ceases to be polynomial. Thus Theorem 3.3 as stated is unsupported; the honest deliverable of this reduction is the constant-factor hardness of Corollary 3.15.
  3. [§5.1, Lemmas 5.3–5.5] The online lower-bound construction also fails for a more concrete reason. In each gadget D_i, all m chains have total length exactly 2^m, irrespective of their skinny-job length. Even if the algorithm does not know the random blocking chain, it can run all m chains of D_i in parallel as soon as they are revealed; the blocking chain then completes in time 2^m along with every other chain in the gadget. Hence the expected time between end(i-1) and end(i) is 2^m, not Ω(m·2^m). Lemma 5.3 is consistent with this, since it gives an expectation of at least m/4 completed chains, but Lemma 5.4's step from m/4 completed chains to m/4·2^m time is precisely the false incompatibility assumption. The claimed Ω(m) competitive ratio therefore does not follow; the construction gives only an Ω(1) lower bound.
minor comments (4)
  1. [§1.1 and §2] The paper repeatedly motivates chains by asserting that 'if the chains are of different types, the makespan is Ω(p·x)', but this statement is used in the technical overview before being proved. After Property 2.3 is shown false, the overview should be revised.
  2. [§1, zero-time jobs] The 'without loss of generality' reduction for zero-time jobs only converts zero-length jobs to jobs of length 1; it does not restore the claimed incompatibility of different chain types. This should be stated explicitly, since the whole paper relies on zero-length fat jobs.
  3. [§3.2.1, Lemma 3.5] The proof of Lemma 3.5 is incomplete: when moving a job v to a later partition to restore the deleted precedence u≺v, the proof does not check the outgoing edges of v. The lemma may be true, but the argument should handle successors of v or be rewritten.
  4. [Throughout] There are many typographical issues, including misplaced braces, inconsistent notation (OPT vs opt, D_j vs T_Dj), and undefined symbols such as 'ℓ' in the statement of Theorem 5.1. These should be cleaned up in any revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; central derivation rests on external LTS/SCS hardness and Yao's principle.

full rationale

The paper's chains are an internal reduction tool, not a fitted or predicted quantity. Offline hardness (Theorems 3.3 and 3.16) is obtained by approximation-preserving reduction from the LTS problem, with the LTS hardness theorem imported from Bhatia et al. [12]. The SCS connection (Theorem 4.1) is a conditional reduction from SCS to scheduling, and the online lower bound (Theorem 5.1) uses Yao's minimax principle on an explicitly constructed randomized DAG. No parameter is fitted to data, and no later claim is definitionally equal to an earlier input. The only self-citation is the provenance footnote [23] (the SPAA 2025 version) plus citations to the authors' earlier paging work in related-work discussion; none of these is load-bearing, since no central theorem is justified by [23]. The main weaknesses of the paper are correctness/soundness issues, not circularity: Property 2.3's incompatibility claim is questionable under the paper's own definition of skinny jobs, and the proof of Theorem 3.3 uses a fixed constant number rho of LTS machines, so tmax <= 2^rho = O(1) and the o((log tmax)^alpha) scaling is not established. These should be assessed as correctness risks; they are not cases where a prediction reduces to its input by construction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The paper's central claims rest on the chains gadget and on transformations from LTS. The chains incompatibility assumption is the most fragile element and is contradicted by a simple parallel schedule. The other axioms are standard complexity-theoretic tools or external hardness results.

assumptions (4)
  • standard math Yao's minimax principle
    Used in Section 5 to convert deterministic lower bounds on a distribution into randomized lower bounds.
  • domain assumption LTS hardness (Theorem 3.2 from Bhatia et al.)
    The offline reductions assume the rho^alpha inapproximability for loading time scheduling.
  • ad hoc to paper Chains of different types are incompatible (Property 2.3)
    The central gadget premise; false as stated because skinny jobs from different chains run in parallel, so the claimed Omega(sum) makespan does not hold.
  • ad hoc to paper Conflict-free DAG transformation preserves LTS optimum (Lemma 3.5)
    The proof moves the second endpoint of a resolved edge without checking outgoing edges; as written it is incomplete and may not preserve optimality in all cases.
invented entities (1)
  • Chains C(m,i) with skinny/fat job pairs
    purpose: Lower bound gadget for offline hardness and online competitive lower bounds
    The paper introduces chains as a new tool. Its key incompatibility property is unproven and false as stated; the gadget is internal to the paper with no external falsifiable handle.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling." pith.science (2026). https://pith.science/paper/B3SBDUSH

@misc{pith2026250901086,
  author       = {Pith},
  title        = {Pith review of: Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/B3SBDUSH}},
  note         = {Machine review of arXiv:2509.01086}
}
abstract

We study the precedence-constrained resource scheduling problem [SICOMP'75]. There are $n$ jobs where each job takes a certain time to finish and has a resource requirement throughout the execution time. There are precedence among the jobs. The problem asks that given a resource budget, schedule the jobs obeying the precedence constraints to minimize makespan (maximum completion time of a job) such that at any point in time, the total resource being used by all the jobs is at most the given resource budget. In the offline setting, an important open question is whether a polynomial-time $O(1)$-factor approximation algorithm can be found. We prove almost tight hardness of approximation: For some constant $\alpha > 0$, there is no $o((\log t_{\max})^{\alpha})$-factor ( or $o( ( \log n )^\alpha )$-factor ) approximation algorithm with $n$ jobs of maximum job length $t_{\max}$, unless P = NP ( or NP $\subset$ DTIME$(O( 2^{\text{polylog}(n)}))$ ). We further show a connection between this scheduling problem and a seemingly unrelated problem called the shortest common super-sequence (SCS) problem, which has wide application in Biology and Genomics. We prove that an $o(\log t_{\max})$-factor approximation of the scheduling problem would imply the existence of an $o(|\Sigma|)$-approximation algorithm for SCS with alphabet $\Sigma$. We then consider the online setting. We present $\Omega(\log n)$ and $\Omega(\log t_{\max})$ lower bounds of the competitive ratio of any randomized online algorithm. Moreover, we present a matching $O(\min\{\log n, \log t_{\max}\})$-competitive deterministic online algorithm.

Figures

Figures reproduced from arXiv: 2509.01086 by the authors.

Figure 1
Figure 1. Figure (a) shows a chain of type 𝐶(𝑚,𝑖). Figure (b) shows how two chains, 𝐶1 of type 𝐶(𝑚,𝑖) and 𝐶2 of type 𝐶(𝑚 ′ , 𝑗) are connected if 𝐶1 ≺ 𝐶2: The sink node of 𝐶1 has precedence over the source node of 𝐶2. Figure (c) shows the optimal way to schedule a set of chains whose skinny jobs have the same length. Figure (d) shows that skinny job 𝑎 can be started at the same time when 𝑏 starts (for proof of Lemma 2.2). Figu… view at source ↗
Figure 2
Figure 2. Part (a): edge (𝑢, 𝑣) is a bonded edge. Part (b) Resolving bonded edge (𝑢, 𝑣). We still need to perform an additional transformation of the intermediate LTS problem with a conflict-free graph. Specifically, the loading times of the machines may not be bounded. To ensure our reduction has polynomial in the input size, we want the loading times to be upper-bounded by a polynomial in the problem size, i.e., polynomial … view at source ↗
Figure 3
Figure 3. Part (a) depicts a chain of type 𝐶(𝜌,𝑖) in 𝐷ℓ that corresponds to character 𝑖 in sequence ℓ. Part (b) shows characters ℓ𝑖 and ℓ𝑖+1 from input sequence ℓ = . . . , ℓ𝑖 , ℓ𝑖+1, . . . are replaced with two chains in 𝐷ℓ . Theorem 4.1. For any fixed 𝜌 ∈ N, if there exists a polynomial-time 𝑜(log𝑡max)-approximation algorithm for the resource scheduling problem with maximum job size 𝑡max = 2 𝜌 , then there exists a polynomi… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Part (a) shows a 𝐷𝑖 . Part (b) shows how 𝐷𝑖 ’s are connected to each other. In 𝐷𝑖−1, chain 𝐶𝑗 contains end(𝑖 − 1). In 𝐷𝑖 , chain 𝐶𝑗 ′ contains end(𝑖). We now prove the main theorem (conditional lower bound for resource scheduling problem) of this section. Proof of Theo…
Figure 5
Figure 5. Figure 5: Lower bound construction of greedy algorithms [PITH_FULL_IMAGE:figures/full_fig_p033_5.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

66 extracted references · 65 canonical work pages

  1. [1]

    Brief announcement: Green paging and parallel paging

    Kunal Agrawal, Michael Bender, Rathish Das, William Kuszmaul, Enoch Peserico, and Michele Scquizzato. Brief announcement: Green paging and parallel paging. In Proc. 32st ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020

    work page 2020

  2. [2]

    Tight bounds of parallel paging and green paging

    Kunal Agrawal, Michael Bender, Rathish Das, William Kuszmaul, Enoch Peserico, and Michele Scquizzato. Tight bounds of parallel paging and green paging. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021

    work page 2021

  3. [3]

    Bender, Rathish Das, William Kuszmaul, Enoch Peserico, and Michele Scquizzato

    Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, and Michele Scquizzato. Online parallel paging with optimal makespan. In Kunal Agrawal and I-Ting Angelina Lee, editors, Proc. 34th ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA), Philadelphia, PA, USA, July 11 - 14, 2022 , pages 205–216

    work page 2022

  4. [4]

    Task scheduling techniques in cloud computing: A literature survey

    AR Arunarani, Dhanabalachandran Manjula, and Vijayan Sugumaran. Task scheduling techniques in cloud computing: A literature survey. Future Generation Computer Systems , 91:407–415, 2019

    work page 2019

  5. [5]

    Strip packing with precedence constraints and strip packing with release times

    John Augustine, Sudarshan Banerjee, and Sandy Irani. Strip packing with precedence constraints and strip packing with release times. In Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures , pages 180–189, 2006

    work page 2006

  6. [6]

    On-line scheduling with precedence constraints

    Yossi Azar and Leah Epstein. On-line scheduling with precedence constraints. Discrete Applied Mathematics, 119(1- 2):169–180, 2002

    work page 2002

  7. [7]

    Shelf algorithms for two-dimensional packing problems

    Brenda S Baker and Jerald S Schwarz. Shelf algorithms for two-dimensional packing problems. SIAM Journal on Computing, 12(3):508–525, 1983

    work page 1983

  8. [8]

    An approximate algorithm for the partitionable independent task scheduling problem

    KPBP Banerjee. An approximate algorithm for the partitionable independent task scheduling problem. Urbana, 51:61801, 1990

    work page 1990

Show all 66 references
  1. [9]

    An approximation algorithm for the shortest common supersequence problem: an experimental analysis

    Paolo Barone, Paola Bonizzoni, Gianluca Delta Vedova, and Giancarlo Mauri. An approximation algorithm for the shortest common supersequence problem: an experimental analysis. In Proceedings of the 2001 ACM Symposium on Applied Computing, SAC ’01, page 56–60, New York, NY, USA,...

    2001

  2. [10]

    Scheduling cilk multithreaded parallel programs on processors of different speeds

    Michael A Bender and Michael O Rabin. Scheduling cilk multithreaded parallel programs on processors of different speeds. In Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures , pages 13–21, 2000

    2000

  3. [11]

    Hoard: A scalable memory allocator for multithreaded applications

    Emery D Berger, Kathryn S McKinley, Robert D Blumofe, and Paul R Wilson. Hoard: A scalable memory allocator for multithreaded applications. ACM Sigplan Notices, 35(11):117–128, 2000

    2000

  4. [12]

    Bhatia, S

    R. Bhatia, S. Khuller, and J. Naor. The loading time scheduling problem. In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 72–81, 1995

    1995

  5. [13]

    Cilk: An efficient multithreaded runtime system

    Robert D Blumofe, Christopher F Joerg, Bradley C Kuszmaul, Charles E Leiserson, Keith H Randall, and Yuli Zhou. Cilk: An efficient multithreaded runtime system. ACM SigPlan Notices, 30(8):207–216, 1995

    1995

  6. [14]

    Space-efficient scheduling of multithreaded computations

    Robert D Blumofe and Charles E Leiserson. Space-efficient scheduling of multithreaded computations. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing , pages 362–371, 1993

    1993

  7. [15]

    Scheduling multithreaded computations by work stealing

    Robert D Blumofe and Charles E Leiserson. Scheduling multithreaded computations by work stealing. Journal of the ACM (JACM), 46(5):720–748, 1999

    1999

  8. [16]

    Resource-constrained project scheduling: Notation, classification, models, and methods

    Peter Brucker, Andreas Drexl, Rolf Möhring, Klaus Neumann, and Erwin Pesch. Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research , 112(1):3–41, 1999

    1999

  9. [17]

    On multidimensional packing problems

    Chandra Chekuri and Sanjeev Khanna. On multidimensional packing problems. SIAM journal on computing, 33(4):837– 851, 2004

    2004

  10. [18]

    A 3.42-approximation algorithm for scheduling malleable tasks under precedence constraints

    Chi-Yeh Chen and Chih-Ping Chu. A 3.42-approximation algorithm for scheduling malleable tasks under precedence constraints. IEEE Transactions on Parallel and Distributed Systems , 24(8):1479–1488, 2013

    2013

  11. [19]

    Approximation and online algorithms for multidimensional bin packing: A survey

    Henrik I Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali. Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review, 24:63–79, 2017

    2017

  12. [20]

    Introduction to algorithms

    Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022

    2022

  13. [21]

    Shelf algorithms for on-line strip packing

    János Csirik and Gerhard J Woeginger. Shelf algorithms for on-line strip packing. Information Processing Letters , 63(4):171–175, 1997

    1997

  14. [22]

    How to manage high-bandwidth memory automatically

    Rathish Das, Kunal Agrawal, Michael Bender, Jonathan Berry, Benjamin Moseley, and Cynthia Phillips. How to manage high-bandwidth memory automatically. In Proc. 32st ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020

    2020

  15. [23]

    Approximation hardness of resource scheduling

    Rathish Das and Hao Sun. Approximation hardness of resource scheduling. In Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures , pages 46–61, 2025

    2025

  16. [24]

    Data races and the discrete resource-time tradeoff problem with resource reuse over paths

    Rathish Das, Shih-Yu Tsai, Sharmila Duppala, Jayson Lynch, Esther M Arkin, Rezaul Chowdhury, Joseph SB Mitchell, and Steven Skiena. Data races and the discrete resource-time tradeoff problem with resource reuse over paths. In Proc. 31st ACM on Symposium on Parallelism in Algor...

    2019

  17. [25]

    Bender, Jonathan W

    Daniel DeLayo, Kenny Zhang, Kunal Agrawal, Michael A. Bender, Jonathan W. Berry, Rathish Das, Benjamin Moseley, and Cynthia A. Phillips. Automatic HBM management: Models and algorithms. In Kunal Agrawal and I-Ting Angelina Lee, editors, SPAA ’22: 34th ACM Symposium on Parallel...

    2022

  18. [26]

    Approximation algorithms for scheduling with resource and precedence constraints

    Gökalp Demirci, Henry Hoffmann, and David HK Kim. Approximation algorithms for scheduling with resource and precedence constraints. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018

    2018

  19. [27]

    Approximation algorithms for capacitated k-median and scheduling with resource and precedence constraints

    Huseyin Gokalp Demirci. Approximation algorithms for capacitated k-median and scheduling with resource and precedence constraints

  20. [28]

    Dynamic sharing of gpus in cloud systems

    Khaled M Diab, M Mustafa Rafique, and Mohamed Hefeeda. Dynamic sharing of gpus in cloud systems. In 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum , pages 947–954. IEEE, 2013

    2013

  21. [29]

    Jianzhong Du and Joseph Y.-T. Leung. Complexity of scheduling parallel task systems. SIAM Journal on Discrete Mathematics, 2(4):473–487, 1989

    1989

  22. [30]

    Lower bounds for on-line scheduling with precedence constraints on identical machines

    Leah Epstein. Lower bounds for on-line scheduling with precedence constraints on identical machines. InApproximation Algorithms for Combinatiorial Optimization: International Workshop APPROX’98 Aalborg, Denmark, July 18–19, 1998 Proceedings 1, pages 89–98. Springer, 1998

    1998

  23. [31]

    A note on on-line scheduling with precedence constraints on identical machines

    Leah Epstein. A note on on-line scheduling with precedence constraints on identical machines. Information processing letters, 76(4-6):149–153, 2000

    2000

  24. [32]

    Optimal online scheduling of parallel jobs with dependencies

    Anja Feldmann, Ming-Yang Kao, Jirí Sgall, and Shang-Hua Teng. Optimal online scheduling of parallel jobs with dependencies. In S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal, editors, Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18,...

    1993

  25. [33]

    The implementation of the cilk-5 multithreaded language

    Matteo Frigo, Charles E Leiserson, and Keith H Randall. The implementation of the cilk-5 multithreaded language. In Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation , pages 212–223, 1998

    1998

  26. [34]

    Michael R Garey and Ronald L. Graham. Bounds for multiprocessor scheduling with resource constraints. SIAM Journal on Computing, 4(2):187–200, 1975

    1975

  27. [35]

    Improved approximation results on the shortest common supersequence problem

    Zvi Gotthilf and Moshe Lewenstein. Improved approximation results on the shortest common supersequence problem. In Jussi Karlgren, Jorma Tarhio, and Heikki Hyyrö, editors, String Processing and Information Retrieval , pages 277–284, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg

    2009

  28. [36]

    Bounds for certain multiprocessing anomalies

    Ronald L Graham. Bounds for certain multiprocessing anomalies. Bell system technical journal , 45(9):1563–1581, 1966

    1966

  29. [37]

    Scheduling to minimize average completion time: Off-line and on-line approximation algorithms

    Leslie A Hall, Andreas S Schulz, David B Shmoys, and Joel Wein. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Mathematics of operations research , 22(3):513–544, 1997

    1997

  30. [38]

    Strip packing vs

    Xin Han, Kazuo Iwama, Deshi Ye, and Guochuan Zhang. Strip packing vs. bin packing. In Algorithmic Aspects in Information and Management: Third International Conference, AAIM 2007, Portland, OR, USA, June 6-8, 2007. Proceedings 3, pages 358–367. Springer, 2007

    2007

  31. [39]

    Online algorithm for parallel job scheduling and strip packing

    Johann L Hurink and Jacob Jan Paulus. Online algorithm for parallel job scheduling and strip packing. InApproximation and Online Algorithms: 5th International Workshop, W AOA 2007, Eilat, Israel, October 11-12, 2007. Revised Papers 5 , pages 67–74. Springer, 2008

    2007

  32. [40]

    Tight bounds for online vector scheduling

    Sungjin Im, Nathaniel Kell, Janardhan Kulkarni, and Debmalya Panigrahi. Tight bounds for online vector scheduling. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages 525–544. IEEE, 2015

    2015

  33. [41]

    Linear-time approximation schemes for scheduling malleable parallel tasks

    Jansen and Porkolab. Linear-time approximation schemes for scheduling malleable parallel tasks. Algorithmica, 32:507–520, 2002

    2002

  34. [42]

    Scheduling malleable parallel tasks: An asymptotic fully polynomial time approximation scheme

    Klaus Jansen. Scheduling malleable parallel tasks: An asymptotic fully polynomial time approximation scheme. Algorithmica, 39:59–81, 2004

    2004

  35. [43]

    Approximation schemes for machine scheduling with resource (in-) dependent processing times

    Klaus Jansen, Marten Maack, and Malin Rau. Approximation schemes for machine scheduling with resource (in-) dependent processing times. ACM Transactions on Algorithms (TALG), 15(3):1–28, 2019

    2019

  36. [44]

    An approximation algorithm for scheduling malleable tasks under general precedence constraints

    Klaus Jansen and Hu Zhang. An approximation algorithm for scheduling malleable tasks under general precedence constraints. ACM Trans. Algorithms, 2(3):416–434, jul 2006

    2006

  37. [45]

    On the approximation of shortest common supersequences and longest common subsequences

    Tao Jiang and Ming Li. On the approximation of shortest common supersequences and longest common subsequences. SIAM Journal on Computing , 24(5):1122–1139, 1995

    1995

  38. [46]

    Scheduling tasks with precedence constraints on hybrid multi-core machines

    Safia Kedad-Sidhoum, Florence Monna, and Denis Trystram. Scheduling tasks with precedence constraints on hybrid multi-core machines. In 2015 IEEE International Parallel and Distributed Processing Symposium Workshop , pages 27–33, 2015

    2015

  39. [47]

    An integrated survey of deterministic project scheduling

    R Kolisch and R Padman. An integrated survey of deterministic project scheduling. Omega, 29(3):249–272, 2001

    2001

  40. [48]

    Minimalistic predictions to schedule jobs with online precedence constraints

    Alexandra Anna Lassota, Alexander Lindermayr, Nicole Megow, and Jens Schlöter. Minimalistic predictions to schedule jobs with online precedence constraints. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Inte...

    2023

  41. [49]

    J. K. Lenstra and A. H. G. Rinnooy Kan. Complexity of scheduling under precedence constraints. Operations Research, 26(1):22–35, 1978

    1978

  42. [50]

    An approximation algorithm for scheduling trees of malleable tasks

    Renaud Lepère, Grégory Mounié, and Denis Trystram. An approximation algorithm for scheduling trees of malleable tasks. European Journal of Operational Research , 142(2):242–249, 2002

    2002

  43. [51]

    Scheduling malleable and nonmalleable parallel tasks

    Walter Ludwig and Prasoon Tiwari. Scheduling malleable and nonmalleable parallel tasks. In ACM-SIAM Symposium on Discrete Algorithms, 1994

    1994

  44. [52]

    (acyclic) job shops are hard to approximate

    Monaldo Mastrolilli and Ola Svensson. (acyclic) job shops are hard to approximate. In2008 49th Annual IEEE Symposium on Foundations of Computer Science , pages 583–592. IEEE, 2008

    2008

  45. [53]

    Stochastic online scheduling with precedence constraints

    Nicole Megow and Tjark Vredeveld. Stochastic online scheduling with precedence constraints. 2009

    2009

  46. [54]

    Randomized algorithms

    Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms. Cambridge university press, 1995

    1995

  47. [55]

    Efficient approximation algorithms for scheduling malleable tasks

    Gregory Mounie, Christophe Rapine, and Dennis Trystram. Efficient approximation algorithms for scheduling malleable tasks. In Proceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures , SPAA ’99, page 23–32, New York, NY, USA, 1999. Association ...

    1999

  48. [56]

    Scheduling with an orthogonal resource constraint

    Martin Niemeier and Andreas Wiese. Scheduling with an orthogonal resource constraint. Algorithmica, 71:837–858, 2015

    2015

  49. [57]

    Duella P

    M. Duella P. Bonizzoni and G. Mauri. Approximation complexity of longest common subsequence and shortest common supersequence over fixed alphabet. Technical Report 117/94, Università degli Studi Milano, Italy

  50. [58]

    Multi-resource list scheduling of moldable parallel jobs under precedence constraints

    Lucas Perotin, Hongyang Sun, and Padma Raghavan. Multi-resource list scheduling of moldable parallel jobs under precedence constraints. In Proceedings of the 50th International Conference on Parallel Processing , pages 1–10, 2021

    2021

  51. [59]

    A new algorithm for online scheduling of rigid task graphs with near-optimal competitive ratio

    Lucas Perotin, Hongyang Sun, and Padma Raghavan. A new algorithm for online scheduling of rigid task graphs with near-optimal competitive ratio. In Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures, pages 210–224, 2025

    2025

  52. [60]

    Approximation bounds for a general class of precedence constrained parallel machine scheduling problems

    Maurice Queyranne and Andreas S Schulz. Approximation bounds for a general class of precedence constrained parallel machine scheduling problems. SIAM Journal on Computing , 35(5):1241–1253, 2006

    2006

  53. [61]

    The shortest common supersequence problem over binary alphabet is np-complete

    Kari-Jouko Räihä and Esko Ukkonen. The shortest common supersequence problem over binary alphabet is np-complete. Theor. Comput. Sci., 16:187–198, 1981

    1981

  54. [62]

    Scalable locality-conscious multithreaded memory allocation

    Scott Schneider, Christos D Antonopoulos, and Dimitrios S Nikolopoulos. Scalable locality-conscious multithreaded memory allocation. In Proceedings of the 5th international symposium on Memory management , pages 84–94, 2006

    2006

  55. [63]

    Conditional hardness of precedence constrained scheduling on identical machines

    Ola Svensson. Conditional hardness of precedence constrained scheduling on identical machines. In Proceedings of the forty-second ACM symposium on Theory of computing , pages 745–754, 2010

    2010

  56. [64]

    Introduction to cloud computing

    William Voorsluys, James Broberg, and Rajkumar Buyya. Introduction to cloud computing. Cloud computing: Principles and paradigms, pages 1–41, 2011

    2011

  57. [65]

    A note on online strip packing

    Deshi Ye, Xin Han, and Guochuan Zhang. A note on online strip packing. Journal of Combinatorial Optimization , 17(4):417–423, 2009

    2009

  58. [66]

    Multimedia cloud computing

    Wenwu Zhu, Chong Luo, Jianfeng Wang, and Shipeng Li. Multimedia cloud computing. IEEE Signal Processing Magazine, 28(3):59–69, 2011. , Vol. 1, No. 1, Article . Publication date: September 2025

    2011

Pith tools

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