While this submission is a draft, it cannot be used by other submissions.

Hardness of P | M_j | Σ w_j Z_j under the standard reading

Lax434175.IsemStandard · concepts/Lax434175/IsemStandard.lean · lax-434175

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    Interval scheduling with eligible machine sets is the problem P∣Mj∣∑wjZjP \mid M_j \mid \sum w_j Z_j read on the words of lax-888481 (IsemLinkIsemLink). Its hardness carries to the zoo's problem under the standard reading by a word map computed in polynomial time on the word RAM: drop the machines no job may use and renumber the others, then write the standard word of the instance with the threshold ∑jwj−W\sum_j w_j - W. Dropping the unused machines keeps the answer and does not raise the number of machines or the largest processing time.

    Theorem. Under the standard reading, P∣Mj∣∑wjZjP \mid M_j \mid \sum w_j Z_j is W[1]-hard parameterized by the number of machines.

    Theorem. Under the standard reading, P∣Mj∣∑wjZjP \mid M_j \mid \sum w_j Z_j is NP-hard on the instances whose processing times are at most 2525, so para-NP-hard parameterized by the largest processing time.

    Fixed-parameter tractability goes the other way, from the standard reading to the words of interval scheduling, where every job has positive length. Under the standard reading a job may have length zero: it is then a point, which a job running strictly across it blocks, and which no other point blocks. So the points with the same due date and the same machines are one point with their total weight. Scaling all times by K=2r+3K = 2r + 3, where r=min⁡(n,2m)r = \min(n, 2^m) bounds the number of such points at one time, turns every job of positive length [a,d][a, d] into [Ka+r+1,Kd−r−1)[Ka + r + 1, Kd - r - 1) and the ss-th point at time tt into [Kt+s,Kt+s+1)[Kt + s, Kt + s + 1): two jobs overlap after scaling exactly when they clash before. Jobs that can never be on time, and points other than the first of their kind, become jobs without a machine, which padding (as in IsemLinkIsemLink) gives a new machine of their own. The number of machines grows by one and the largest processing time by the factor K≤2⋅2m+3K \le 2 \cdot 2^m + 3.

    Theorem. Under the standard reading, P∣Mj∣∑wjZjP \mid M_j \mid \sum w_j Z_j is fixed-parameter tractable parameterized by the number of machines plus the largest processing time.

    Concept map
    62 concepts; 1 descendant hidden
    100%
    Conjunctive normal formAssembling problems from fieldsOne family for serial and parallel batchingBatching problems in three-field notationBatch scheduling on a single machineCommunication delaysBounds on the number of machines and jobsDeadlinesForbidden times and input encodingsInterruption as a field of parallel-machineschedulingHardness of P | M_j | Σ w_j Z_j under thestandard readingScheduling kernelsMaximizing the minimum machine loadMachine sets and multiprocessor tasksConstraint modules and objectivesNon-preemptive scheduling on parallelmachinesCompletion-time objectivesOnline scheduling as a gameScheduling with operationsOne family for parallel machines and shopsOne family for parallel machines with andwithout preemptionParallel machinesProblems on parallel machines in three-fieldnotationParameters along embeddingsPrecedence constraints and time lagsPreemptive scheduling on parallel machinesPreemptive shop problems in three-fieldnotationPreemptive shop schedulingOptimization problems and embeddingsSingle-machine scheduling with rejectionRelease datesPreemption with restarts on parallelmachinesParameters of the zoo's resultsThe kinds of results on scheduling problemsA single server with setup timesNo-idle shops and batch setup timesOne family for shops with and withoutpreemptionShop problems in three-field notationShop schedulingThe standard reading of scheduling instancesand schedulesThreshold reductions between objectivesTransportation delays and a transport robotScheduling problems as parameterizedproblems on wordsThe Scheduling Zoo, non-preemptiveproblems on parallel machinesResults of The Scheduling Zoo,non-preemptive problems on parallelmachinesParameters of scheduling problemsBinary encoding of an input and a certificateThe complexity class NPThe complexity class PFixed-Parameter Time on the Word RAMFPT-Reductions, FPT, Hardness andCompletenessFinite Relational StructuresFirst-Order Formulas and the Classes Σ_tand Π_tModel Checking and Weighted FaginDefinabilityThe W-Hierarchy and the A-HierarchyNP-Hardness of a Problem on Words ofNumbersBinary encoding of finite wordsPolynomial-time computation by a wordRAMPolynomial-time computation by a TuringmachineThe word RAMComputing a function within a time boundParameterized Problems andFPT-Reductions on a Word RAM
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Lean source view on GitHub

    1import Lax434175.ZooParallel
    2import Lax434175.Results
    3import Lax434175.ResultParameters
    4import Lax434175.StandardReading
    5import Lax434175.ZooParallelResults
    6
    7/-!
    8---
    9title: Hardness of P | M_j | Σ w_j Z_j under the standard reading
    10type: theorem
    11---
    12Interval scheduling with eligible machine sets is the problem P∣Mj∣∑wjZjP \mid M_j \mid \sum w_j Z_j
    13read on the words of lax-888481 (`IsemLink`). Its hardness carries to the zoo's problem
    14under the standard reading by a word map computed in polynomial time on the word RAM: drop
    15the machines no job may use and renumber the others, then write the standard word of the
    16instance with the threshold ∑jwj−W\sum_j w_j - W. Dropping the unused machines keeps the answer
    17and does not raise the number of machines or the largest processing time.
    18
    19**Theorem.** Under the standard reading, P∣Mj∣∑wjZjP \mid M_j \mid \sum w_j Z_j is W[1]-hard
    20parameterized by the number of machines.
    21
    22**Theorem.** Under the standard reading, P∣Mj∣∑wjZjP \mid M_j \mid \sum w_j Z_j is NP-hard on the
    23instances whose processing times are at most 2525, so para-NP-hard parameterized by the
    24largest processing time.
    25
    26Fixed-parameter tractability goes the other way, from the standard reading to the words of
    27interval scheduling, where every job has positive length. Under the standard reading a job may
    28have length zero: it is then a point, which a job running strictly across it blocks, and which
    29no other point blocks. So the points with the same due date and the same machines are one point
    30with their total weight. Scaling all times by K=2r+3K = 2r + 3, where r=min⁡(n,2m)r = \min(n, 2^m) bounds
    31the number of such points at one time, turns every job of positive length [a,d][a, d] into
    32[Ka+r+1,Kd−r−1)[Ka + r + 1, Kd - r - 1) and the ss-th point at time tt into [Kt+s,Kt+s+1)[Kt + s, Kt + s + 1): two
    33jobs overlap after scaling exactly when they clash before. Jobs that can never be on time, and
    34points other than the first of their kind, become jobs without a machine, which padding (as in
    35`IsemLink`) gives a new machine of their own. The number of machines grows by one and the
    36largest processing time by the factor K≤2⋅2m+3K \le 2 \cdot 2^m + 3.
    37
    38**Theorem.** Under the standard reading, P∣Mj∣∑wjZjP \mid M_j \mid \sum w_j Z_j is fixed-parameter
    39tractable parameterized by the number of machines plus the largest processing time.
    40-/
    41
    42namespace Lax434175.IsemStandard
    43open Lax434175 Lax434175.Results Lax434175.ResultParameters
    44
    45-- zoo-result: {"problem": "P|M_j|\\sum w_jZ_j", "param": "m", "claim": "is W[1]-hard", "note": "Multicoloured Clique (W[1]-complete in lax-496464) fpt-reduces to it. The cited result says strongly W[1]-hard, which is proved as well (IsemStrong.p200_r0_holds)."}
    46axiom wHard_m :
    47 WHard (StandardReading.ops.at ZooParallel.p200) 1 (lift (Ops.m ZooParallel.p200))
    48
    49-- zoo-result: {"problem": "P|M_j|\\sum w_jZ_j", "param": "pmax", "claim": "is para-NP-hard"}
    50axiom paraNPHard_pmax :
    51 ParaNPHard (StandardReading.ops.at ZooParallel.p200) (lift (Ops.pmax ZooParallel.p200))
    52
    53-- zoo-result: {"problem": "P|M_j|\\sum w_jZ_j", "param": "m+pmax", "claim": "is fixed parameter tractable"}
    54axiom fpt_mPmax : Lax434175.ZooParallelResults.p200_r1 StandardReading.ops
    55
    56end Lax434175.IsemStandard
    57
    Show ProofShow ProofShow Proof

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…