pith. sign in

arxiv: 1907.03526 · v1 · pith:WQJI5LV5new · submitted 2019-07-08 · 💻 cs.CC · cs.DS

Inapproximability Results for Scheduling with Interval and Resource Restrictions

Marten Maack , Klaus Jansen This is my paper

Pith reviewed 2026-05-25 00:44 UTC · model grok-4.3

classification 💻 cs.CC cs.DS
keywords restricted assignmentinterval restrictionsresource restrictionsinapproximabilityPTASmakespan minimizationSanta Claus problem
0
0 comments X

The pith

Scheduling with interval eligibility has no PTAS unless P equals NP.

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

The paper studies the restricted assignment problem of assigning jobs to eligible machines to minimize the makespan. It focuses on two structured variants of eligibility constraints. For interval restrictions, where eligible machines form consecutive blocks, the work proves there is no polynomial-time approximation scheme. For resource restrictions with multiple capacities, it derives specific constant inapproximability thresholds.

Core claim

The restricted assignment problem with interval restrictions admits no PTAS unless P=NP. The resource-restricted variant admits no approximation ratio better than 48/47 with two resources and no better than 1.5 with four resources, unless P=NP. Both sets of results carry over to the corresponding Santa Claus maximization problems.

What carries the argument

NP-hardness reductions from known hard partitioning problems that encode the interval or resource constraints into job-machine eligibility while preserving the makespan objective.

If this is right

  • Interval eligibility does not suffice for a PTAS in restricted assignment.
  • Resource restrictions with two or four resources inherit constant-factor hardness.
  • The same inapproximability statements hold for the Santa Claus objective of maximizing the minimum machine load.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Special cases known to have PTAS must exploit structure beyond mere intervals or low numbers of resources.
  • The reductions may adapt to show hardness for other objectives such as total completion time.
  • Parameterized algorithms could target the number of distinct intervals or resources as the parameter.

Load-bearing premise

That P is not equal to NP.

What would settle it

A polynomial-time algorithm that achieves an approximation ratio arbitrarily close to 1 for the interval-restricted problem on some infinite family of instances.

Figures

Figures reproduced from arXiv: 1907.03526 by Klaus Jansen, Marten Maack.

Figure 4
Figure 4. Figure 4: The left picture visualizes that each RAI instance can be seen as a RAR(2) instance and the right one depicts an RAR(2) instance that is not a RAI instance. In both pictures, each dimension corresponds to a resource, the squares mark the capacities of machines and the circles the demands of jobs. If the capacity of a machine is at least as big as the demand of a job in both dimension, the job is eligible o… view at source ↗
read the original abstract

In the restricted assignment problem, the input consists of a set of machines and a set of jobs each with a processing time and a subset of eligible machines. The goal is to find an assignment of the jobs to the machines minimizing the makespan, that is, the maximum summed up processing time any machine receives. Herein, jobs should only be assigned to those machines on which they are eligible. It is well-known that there is no polynomial time approximation algorithm with an approximation guarantee of less than 1.5 for the restricted assignment problem unless P=NP. In this work, we show hardness results for variants of the restricted assignment problem with particular types of restrictions. In the case of interval restrictions the machines can be totally ordered such that jobs are eligible on consecutive machines. We resolve the open question of whether the problem admits a polynomial time approximation scheme (PTAS) in the negative (unless P=NP). There are several special cases of this problem known to admit a PTAS. Furthermore, we consider a variant with resource restriction where each machine has capacities and each job demands for a fixed number of resources. A job is eligible on a machine if its demand is at most the capacity of the machine for each resource. For one resource, this problem is known to admit a PTAS, for two, the case of interval restrictions is contained, and in general, the problem is closely related to unrelated scheduling with a low rank processing time matrix. We show that there is no polynomial time approximation algorithm with a rate smaller than 48/47 or 1.5 for scheduling with resource restrictions with 2 or 4 resources, respectively, unless P=NP. All our results can be extended to the so called Santa Claus variants of the problems where the goal is to maximize the minimal processing time any machine receives.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper studies inapproximability for the restricted assignment problem under two types of restrictions. For interval restrictions (machines ordered so that eligible machines for each job form an interval), it claims there is no PTAS unless P=NP, resolving an open question. For resource restrictions (machines have capacities per resource, jobs have demands), it claims inapproximability thresholds of 48/47 (2 resources) and 1.5 (4 resources) unless P=NP. All results extend to the Santa Claus maximization variants.

Significance. If the reductions are correct, the results are significant: they close the PTAS question for interval restrictions (noting that several special cases already admit PTASes) and give the first constant-factor hardness for the resource-restricted model with small numbers of resources, which is related to low-rank unrelated scheduling. The Santa Claus extensions broaden the applicability.

major comments (2)
  1. [interval restrictions section] The abstract asserts a negative PTAS result for interval restrictions, but a no-PTAS claim requires an approximation-preserving reduction that maps yes-instances to makespan ≤ B and no-instances to makespan ≥ (1+ε)B for some fixed ε>0 independent of n. The manuscript must exhibit this fixed-gap construction explicitly (rather than a plain NP-completeness reduction) in the interval-restrictions section; otherwise the resolution of the open question does not follow.
  2. [resource restrictions section] For the resource-restriction hardness results, the claimed ratios 48/47 (2 resources) and 1.5 (4 resources) must be shown to arise from gap-producing reductions; the manuscript should state the source problem, the gap value, and why the reduction is approximation-preserving in the relevant theorem statements.
minor comments (2)
  1. [abstract / introduction] The abstract mentions that 'several special cases of this problem known to admit a PTAS' but does not cite them; add references in the introduction.
  2. [Santa Claus variants paragraph] Notation for the Santa Claus variants should be introduced once and used consistently when stating the extensions of the hardness results.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the two major comments point by point below and will make the requested clarifications in the revised version.

read point-by-point responses

  1. Referee: [interval restrictions section] The abstract asserts a negative PTAS result for interval restrictions, but a no-PTAS claim requires an approximation-preserving reduction that maps yes-instances to makespan ≤ B and no-instances to makespan ≥ (1+ε)B for some fixed ε>0 independent of n. The manuscript must exhibit this fixed-gap construction explicitly (rather than a plain NP-completeness reduction) in the interval-restrictions section; otherwise the resolution of the open question does not follow.

    Authors: We thank the referee for highlighting this point. The reduction in Section 3 is an approximation-preserving reduction from a gap version of 3-Partition (or the appropriate source problem) that produces a fixed gap of 3/2 independent of n. To make this explicit as requested, we will revise the relevant theorem statement and add a short paragraph in the interval-restrictions section explaining the fixed gap and why the reduction is approximation-preserving. revision: yes

  2. Referee: [resource restrictions section] For the resource-restriction hardness results, the claimed ratios 48/47 (2 resources) and 1.5 (4 resources) must be shown to arise from gap-producing reductions; the manuscript should state the source problem, the gap value, and why the reduction is approximation-preserving in the relevant theorem statements.

    Authors: We agree that the theorem statements would benefit from greater explicitness. The 48/47 and 1.5 ratios are obtained from approximation-preserving reductions from known constant-factor inapproximability results for other scheduling problems. In the revised manuscript we will update the theorem statements for both the 2-resource and 4-resource cases to name the source problem, restate the exact gap values, and briefly note that the reductions preserve the approximation gap. revision: yes

Circularity Check

0 steps flagged

Standard reduction-based inapproximability; no circularity

full rationale

The paper establishes its central negative PTAS result for interval restrictions and the inapproximability bounds for resource restrictions exclusively via approximation-preserving reductions from externally known NP-complete problems. These reductions introduce fixed gaps independent of the target bounds and do not rely on self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations whose validity depends on the present work. The derivation chain is therefore self-contained against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The results rest on the standard assumption P ≠ NP and on the existence of suitable NP-hard source problems for the reductions; no free parameters or invented entities appear in the abstract.

axioms (1)
  • domain assumption P ≠ NP
    Invoked to translate NP-hardness into inapproximability statements for both the interval and resource cases.

pith-pipeline@v0.9.0 · 5864 in / 1095 out tokens · 19128 ms · 2026-05-25T00:44:31.977291+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages · 7 internal anchors

  1. [1]

    2 Aditya Bhaskara, Ravishankar Krishnaswamy, Kunal Talwar, and Udi Wieder

    doi:10.1145/3070694. 2 Aditya Bhaskara, Ravishankar Krishnaswamy, Kunal Talwar, and Udi Wieder. Minimum makespan scheduling with low rank processing times. In Proceedings of the Twenty-Fourth An- nual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013 , pages 937–947,

    work page doi:10.1145/3070694 2013

  2. [2]

    3 Andreas Brandstädt and Vadim V

    doi:10.1137/1.9781611973105.67. 3 Andreas Brandstädt and Vadim V. Lozin. On the linear structu re and clique-width of bipartite permutation graphs. Ars Comb. , 67,

    work page doi:10.1137/1.9781611973105.67

  3. [3]

    On (1, ε)-restricted assignment makespan minimization

    4 Deeparnab Chakrabarty, Sanjeev Khanna, and Shi Li. On (1, ε)-restricted assignment makespan minimization. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Sympo- sium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, J anuary 4-6, 2015 , pages 1087–1101,

    work page 2015

  4. [4]

    Graph Balancing with Two Edge Types

    doi:10.1137/1.9781611973730.73. 5 Deeparnab Chakrabarty and Kirankumar Shiragur. Graph bala ncing with two edge types. CoRR, abs/1604.06918,

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1137/1.9781611973730.73

  5. [5]

    Graph Balancing with Two Edge Types

    arXiv:1604.06918. 6 Lin Chen, Dániel Marx, Deshi Ye, and Guochuan Zhang. Paramet erized and approximation results for scheduling with a low rank processing time matri x. In 34th Symposium on The- oretical Aspects of Computer Science, STACS 2017, March 8-1 1, 2017, Hannover, Germany , pages 22:1–22:14,

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  6. [6]

    7 Lin Chen, Deshi Ye, and Guochuan Zhang

    doi:10.4230/LIPIcs.STACS.2017.22. 7 Lin Chen, Deshi Ye, and Guochuan Zhang. An improved lower bou nd for rank four scheduling. Oper. Res. Lett. , 42(5):348–350,

    work page doi:10.4230/lipics.stacs.2017.22 2017

  7. [7]

    8 Siu-Wing Cheng and Yuchen Mao

    doi:10.1016/j.orl.2014.06.003. 8 Siu-Wing Cheng and Yuchen Mao. Restricted max-min fair allo cation. In 45th Interna- tional Colloquium on Automata, Languages, and Programming , ICALP 2018, July 9-13, 2018, Prague, Czech Republic , pages 37:1–37:13,

    work page doi:10.1016/j.orl.2014.06.003 2014

  8. [8]

    9 Sami Davies, Thomas Rothvoss, and Yihao Zhang

    doi:10.4230/LIPIcs.ICALP.2018.37. 9 Sami Davies, Thomas Rothvoss, and Yihao Zhang. A tale of sant a claus, hypergraphs and matroids. CoRR, abs/1807.07189,

    work page doi:10.4230/lipics.icalp.2018.37 2018

  9. [9]

    10 Tomás Ebenlendr, Marek Krcál, and Jirí Sgall

    arXiv:1807.07189. 10 Tomás Ebenlendr, Marek Krcál, and Jirí Sgall. Graph balanci ng: A special case of scheduling unrelated parallel machines. Algorithmica, 68(1):62–80,

    work page arXiv

  10. [10]

    11 Leah Epstein and Asaf Levin

    doi:10.1007/s00453-012-9668-9. 11 Leah Epstein and Asaf Levin. Scheduling with processing set restrictions: Ptas results for several variants. International Journal of Production Economics , 133(2):586–595,

    work page doi:10.1007/s00453-012-9668-9

  11. [11]

    12 Pinar Heggernes and Dieter Kratsch

    doi:10.1016/j.ijpe.2011.04.024. 12 Pinar Heggernes and Dieter Kratsch. Linear-time certifyin g recognition algorithms and for- bidden induced subgraphs. Nord. J. Comput. , 14(1-2):87–108,

    work page doi:10.1016/j.ijpe.2011.04.024 2011

  12. [12]

    14 Dorit S

    doi:10.1145/7531.7535. 14 Dorit S. Hochbaum and David B. Shmoys. A polynomial approxim ation scheme for scheduling on uniform processors: Using the dual approximation approa ch. SIAM J. Comput. , 17(3):539– 551,

    work page doi:10.1145/7531.7535

  13. [13]

    15 Ellis Horowitz and Sartaj Sahni

    doi:10.1137/0217033. 15 Ellis Horowitz and Sartaj Sahni. Exact and approximate algo rithms for scheduling noniden- tical processors. J. ACM , 23(2):317–327,

    work page doi:10.1137/0217033

  14. [14]

    16 Chien-Chung Huang and Sebastian Ott

    doi:10.1145/321941.321951. 16 Chien-Chung Huang and Sebastian Ott. A combinatorial appro ximation algorithm for graph balancing with light hyper edges. In 24th Annual European Symposium on Al- gorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark , pages 49:1–49:15,

    work page doi:10.1145/321941.321951 2016

  15. [15]

    17 Klaus Jansen, Marten Maack, and Roberto Solis-Oba

    doi:10.4230/LIPIcs.ESA.2016.49. 17 Klaus Jansen, Marten Maack, and Roberto Solis-Oba. Structu ral parameters for schedul- ing with assignment restrictions. In Algorithms and Complexity - 10th International Con- ference, CIAC 2017, Athens, Greece, May 24-26, 2017, Procee dings, pages 357–368,

    work page doi:10.4230/lipics.esa.2016.49 2016

  16. [16]

    Marten Maack and Klaus Jansen 23 18 Klaus Jansen and Lars Rohwedder

    doi:10.1007/978-3-319-57586-5\_30 . Marten Maack and Klaus Jansen 23 18 Klaus Jansen and Lars Rohwedder. On the configuration-lp of t he restricted assignment problem. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposiu m on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19 , pages 2670– 2678,

    work page doi:10.1007/978-3-319-57586-5 2017

  17. [17]

    19 Klaus Jansen and Lars Rohwedder

    doi:10.1137/1.9781611974782.176. 19 Klaus Jansen and Lars Rohwedder. A quasi-polynomial approx imation for the restricted assignment problem. In Integer Programming and Combinatorial Optimization - 19th In- ternational Conference, IPCO 2017, Waterloo, ON, Canada, J une 26-28, 2017, Proceedings , pages 305–316,

    work page doi:10.1137/1.9781611974782.176 2017

  18. [18]

    Local search breaks 1.75 for Graph Balancing

    doi:10.1007/978-3-319-59250-3\_25 . 20 Klaus Jansen and Lars Rohwedder. Local search breaks 1.75 fo r graph balancing. CoRR, abs/1811.00955,

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/978-3-319-59250-3

  19. [19]

    Local search breaks 1.75 for Graph Balancing

    arXiv:1811.00955. 21 Kamyar Khodamoradi. Algorithms for Scheduling and Routing Problems . PhD thesis, Simon Fraser University,

    work page internal anchor Pith review Pith/arXiv arXiv

  20. [20]

    PTAS for ordered instances of resource allocation problems

    22 Kamyar Khodamoradi, Ramesh Krishnamurti, Arash Rafiey, and Georgios Stamoulis. PTAS for ordered instances of resource allocation problems. In IARCS Annual Conference on Foun- dations of Software Technology and Theoretical Computer Sc ience, FSTTCS 2013, December 12-14, 2013, Guwahati, India , pages 461–473,

    work page 2013

  21. [21]

    PTAS for Ordered Instances of Resource Allocation Problems with Restrictions on Inclusions

    doi:10.4230/LIPIcs.FSTTCS.2013.461. 23 Kamyar Khodamoradi, Ramesh Krishnamurti, Arash Rafiey, and Georgios Stamoulis. PTAS for ordered instances of resource allocation problems with restrictions on inclusions. CoRR, abs/1610.00082,

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.4230/lipics.fsttcs.2013.461 2013

  22. [22]

    PTAS for Ordered Instances of Resource Allocation Problems with Restrictions on Inclusions

    arXiv:1610.00082. 24 Kangbok Lee, Joseph Y.-T. Leung, and Michael L. Pinedo. Make span minimiza- tion in online scheduling with machine eligibility. Annals OR , 204(1):189–222,

    work page internal anchor Pith review Pith/arXiv arXiv

  23. [23]

    25 Jan Karel Lenstra, David B

    doi:10.1007/s10479-012-1271-6. 25 Jan Karel Lenstra, David B. Shmoys, and Éva Tardos. Approxim ation algo- rithms for scheduling unrelated parallel machines. Math. Program. , 46:259–271,

    work page doi:10.1007/s10479-012-1271-6

  24. [24]

    26 Joseph Y-T Leung and Chung-Lun Li

    doi:10.1007/BF01585745. 26 Joseph Y-T Leung and Chung-Lun Li. Scheduling with processi ng set restrictions: A survey. International Journal of Production Economics , 116(2):251–262,

    work page doi:10.1007/bf01585745

  25. [25]

    27 Joseph Y-T Leung and Chung-Lun Li

    doi:10.1016/j.ijpe.2008.09.003. 27 Joseph Y-T Leung and Chung-Lun Li. Scheduling with processi ng set restrictions: A literature update. International Journal of Production Economics , 175:1–11,

    work page doi:10.1016/j.ijpe.2008.09.003 2008

  26. [26]

    28 Gabriella Muratore, Ulrich M

    doi:10.1016/j.ijpe.2014.09.038. 28 Gabriella Muratore, Ulrich M. Schwarz, and Gerhard J. Woegi nger. Parallel machine scheduling with nested job assignment restrictions. Oper. Res. Lett. , 38(1):47–50,

    work page doi:10.1016/j.ijpe.2014.09.038 2014

  27. [27]

    29 Jinwen Ou, Joseph Y-T Leung, and Chung-Lun Li

    doi:10.1016/j.orl.2009.09.010. 29 Jinwen Ou, Joseph Y-T Leung, and Chung-Lun Li. Scheduling pa rallel machines with in- clusive processing set restrictions. Naval Research Logistics (NRL) , 55(4):328–338,

    work page doi:10.1016/j.orl.2009.09.010 2009

  28. [28]

    30 Daniel R

    doi:10.1002/nav.20286. 30 Daniel R. Page and Roberto Solis-Oba. A 3/2-approximation a lgorithm for the graph balanc- ing problem with two weights. Algorithms, 9(2):38,

    work page doi:10.1002/nav.20286

  29. [29]

    31 Thomas J

    doi:10.3390/a9020038. 31 Thomas J. Schaefer. The complexity of satisfiability proble ms. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, S an Diego, California, USA, pages 216–226,

    work page doi:10.3390/a9020038 1978

  30. [30]

    32 Petra Schuurman and Gerhard J Woeginger

    doi:10.1145/800133.804350. 32 Petra Schuurman and Gerhard J Woeginger. Polynomial time ap proximation algorithms for machine scheduling: Ten open problems. Journal of Scheduling , 2(5):203–213,

    work page doi:10.1145/800133.804350

  31. [31]

    33 Ulrich M

    doi:10.1002/(SICI)1099-1425(199909/10)2:5<203::AID-JOS26>3.0.CO;2-5 . 33 Ulrich M. Schwarz. Approximation algorithms for scheduling and two- dimensional packing problems . PhD thesis, University of Kiel,

    work page doi:10.1002/(sici)1099-1425(199909/10)2:5

  32. [33]

    A PTAS for Scheduling with Tree Assignment Restrictions

    arXiv:1009.4529. 35 Georgios Stamoulis. Private communication,

    work page internal anchor Pith review Pith/arXiv arXiv

  33. [34]

    37 Craig A

    doi:10.1137/110851201. 37 Craig A. Tovey. A simplified np-complete satisfiability problem. Discrete Applied Mathematics, 8(1):85–89,

    work page doi:10.1137/110851201

  34. [35]

    38 Chao Wang and René Sitters

    doi:10.1016/0166-218X(84)90081-7. 38 Chao Wang and René Sitters. On some special cases of the restr icted assignment problem. Inf. Process. Lett. , 116(11):723–728,

    work page doi:10.1016/0166-218x(84)90081-7

  35. [36]

    39 David P

    doi:10.1016/j.ipl.2016.06.007. 39 David P. Williamson and David B. Shmoys. The Design of Ap- proximation Algorithms . Cambridge University Press,

    work page doi:10.1016/j.ipl.2016.06.007 2016

  36. [37]

    Marten Maack and Klaus Jansen 25 A Examples for Section 2 Example Simple Reduction

    doi:10.1016/S0167-6377(96)00055-7. Marten Maack and Klaus Jansen 25 A Examples for Section 2 Example Simple Reduction. The following formula is an instance of 3-SAT ∗ with minimal size: (¬ x2, ¬ x3, x 1)1 ∧ (¬ x1, x 2, ¬ x3)1 ∧ (x3, ¬ x2, x 1)2 ∧ (¬ x1, x 3, x 2)2 Note that the formula is fulfilled if all the variables take th e value ⊤ . The corresponding...

    work page doi:10.1016/s0167-6377(96)00055-7