Asymmetric Weighted Earliness-Tardiness: Scheduling with a Nonrestrictive Common Due Date

Results at a Glance

• Positive-integer AWET at the boundary due date is strongly NP-complete via a unary-polynomial exact-cover reduction.The result applies to the asymmetric model without ratio-order restrictions.Source: Results at a Glance · p. 2, §2.1 · p. 13
• An anchored SDP with deterministic marginal thresholding gives unrestricted AWET a polynomial-time (3 + 2√2 + ε)-approximation.The rounding uses an anchored local-consistency relaxation and a minimum-kernel covariance inequality tailored to the scheduling objective.Source: Results at a Glance · p. 2, methodology · p. 14
• Under strict reversal of the two ratio orders, AWET is weakly NP-complete and has an exact two-resource pseudopolynomial algorithm.Source: Results at a Glance · p. 2, §3 · p. 15
• For fixed total ratio-order refinements with a separable ratio permutation, exact separating-tree convolution and geometric trimming yield an FPTAS.Source: Results at a Glance · p. 2, High-level contents · p. 4

Why the problem matters

• The canonical early-set objective is the common backbone: unrestricted order is strongly NP-complete but admits a constant-factor approximation, exact reversal is weakly NP-complete, and separable order interaction admits an FPTAS.The optimal cost is the minimum of the canonical objective over nonempty early sets.Source: Why the problem matters · pp. 11–12

3 Contribution map and scope

• For fixed total refinements, AWET admits an FPTAS when the resulting ratio permutation is separable.The contribution map identifies coordinated geometric trimming as part of the approach.Source: §3 · p. 15

Why these results belong together

• The four technical parts share a canonical quadratic objective but investigate its encoding power, relaxation certificates, exact reversal, and order decomposition.The section presents these distinct questions as the reason to read the results together.Source: Why these results belong together · pp. 15–16

5 Overview of the proof

• The reduction converts Restricted Exact Cover by 3-Sets into prefix equations, then encodes each source set as an eight-job block with two balanced orientations.Separated ratio bands create squared prefix-cover errors, while an anchor-coupled minimum-kernel penalty enforces block loads.Source: with a Common Due Date · p. 19, §5 · p. 24

4.2 Main result

• The decision version of positive-integer AWET is strongly NP-complete, and therefore unary NP-hard.This resolves the previously open strong-complexity question for the general asymmetric-weight common-due-date model.Source: §4.2 · p. 22, §4.1 · p. 22

6 A canonical set formulation of AWET

• An optimal AWET schedule can be chosen without internal idle time, with a completion at d and ratio-ordered early and tardy jobs.Once the early set is fixed, the canonical schedule removes the need to optimize over arbitrary start times.Source: §6 · pp. 25–26
• Minimizing the canonical schedule cost over nonempty early-job sets gives the exact AWET optimum.For each such set, ratio orders determine the schedule and its cost; the structural lemma guarantees a globally optimal schedule of this form.Source: §6 · pp. 26–27

7 Reduction I: RXC3 to regular prefix exactness

• RPE orders the RXC3 elements and requires every prefix to contain exactly as many selected incidences as elements.The construction retains the source family and permits any ordering of its elements; cumulative prefix equations are suited to intervals on a scheduling ratio axis.Source: §7 · pp. 28–29, §7.1 · p. 29

7.2 The “if” proof / 7.3 The “only if” proof

• RPE is NP-complete because its prefix equations are equivalent to RXC3 exact cover: exact covers satisfy them, and successive differences recover each row equation.The transformation is polynomial, and a binary vector certifies RPE feasibility.Source: §7.3 · p. 30, §7.2 · p. 30

8 Reduction II: regular prefix exactness to AWET

• The RPE-to-AWET construction uses 8n+1 integer-data jobs: eight state jobs per source set and one global anchor.Its four layers encode balanced block states, element-band occurrences, prefix-square linear fields, and a low-cost assignment restricted to the two-state block structure.Source: §8 · p. 31

8.1.1 Numerical scales

• Separated numerical scales assign distinct roles to block balance, element levels, pair codes, and orientation.The T, M, and Q_h digits encode these roles, while GM separates consecutive element bands from block-index variation.Source: §8.1.1 · p. 32

8.1.2 The eight-job coded block

• Each eight-job block has two complementary canonical orientations, both placing exactly half its processing time on the tardy side.The controller difference of 3 balances the three occurrence differences of 1 each.Source: §8.1.2 · p. 33

8.1.3 Arithmetic synchronization

• A block has zero signed processing load exactly in its two encoded states, as scale separation forces its T- and M-level discrepancies to vanish.The residual terms are too small to cancel a nonzero discrepancy at either scale.Source: §8.1.3 · pp. 34–35
• The arithmetic code forces each pair to split and leaves only two complementary block orientations.The superincreasing pair digits eliminate imbalances, while the final residual selects one of the two orientations.Source: §8.1.3 · p. 35
• A block’s tardy load equals its target exactly when all its jobs take the prescribed signed orientation.The global load lock enforces this load equality, allowing the arithmetic lemma to impose the two-state code.Source: §8.1.3 · pp. 35–36

8.1.4 Early ratios and the minimum-kernel field

• The minimum-kernel field decreases strictly across blocks while remaining bounded in magnitude.The stated bounds are 4T < βv < 5T and 0 < f1 − fn < 10N^2T.Source: §8.1.4 · pp. 36–37

8.1.5 Effective atoms: compressing complete pairs

• The coded-assignment restriction used for compression is algebraic at this stage, not yet a claim about optimal assignments.The global load lock and the later choice of the anchor’s tardiness ratio are stated to justify it for an optimal canonical schedule.Source: §8.1.5 · p. 37
• Complete clusters from different blocks can be replaced by effective atoms without changing their cross-interaction when physical and effective ratio orders agree.This compression preserves cross-block interactions exactly; the physical jobs remain in the schedule and within-block terms remain uncompressed.Source: §8.1.5 · pp. 38–39
• Scale separation orders the element bands above the controller band, with gaps exceeding GM and total within-band width below 15N^3T.The separation also ensures the physical cluster order agrees with the effective-ratio order, enabling exact pair compression.Source: §8.1.5 · pp. 41, 44

8.1.6 Prefix profiles and the main quadratic signal

• Each block’s signed profile accumulates occurrence-atom mass and returns to zero after crossing its controller atom.The controller prevents a spurious tail below the last element band; the cross-block coefficient also admits effective-atom and profile representations.Source: §8.1.6 · p. 44
• Main ratio gaps contribute squares of signed prefix totals, while a matching linear field centers each resulting penalty at the target prefix.Completing the square yields a penalty proportional to (Ck(x) − k)^2.Source: §8.1.6 · p. 46, §8.1.7 · p. 47

8.1.7 Logical-field correction

• The logical-field correction uses a rounded integer adjustment, leaving a bounded field error that can be absorbed into Γ rather than requiring exact cancellation.The rounding error is explicitly bounded.Source: §8.1.7 · pp. 47–48

8.1.8 Tardiness ratios, the anchor, and the load-lock scale

• Block-dependent tardiness ratios fix the tardy block order, and anchor interactions shift the load quadratic’s minimum to the prescribed vector β.The anchor supplies the linear term that centers the minimum-kernel quadratic at β.Source: §8.1.8 · pp. 49, 51
• With the anchor early, every optimum has the prescribed block loads, forcing each block into one of its two coded states.The minimum-kernel quadratic penalizes every nonzero integer load error more than the remaining terms can save.Source: §8.1.8 · pp. 49, 51
• A feasible coded schedule with the anchor early bounds the optimum, so no optimal canonical assignment has the anchor tardy.The benchmark is independent of whether the coded assignment represents an exact cover.Source: §8.1.8 · pp. 51–52

8.1.9 Canonical objective, residual bound, and decision threshold

• After the load lock, every schedule that can be optimal is represented by n logical spins, and the master decomposition is an exact identity.Its residual explicitly contains within-band and rounding terms rather than an omitted asymptotic error.Source: §8.1.9 · pp. 52–53
• One unit of squared prefix error costs more than the largest favorable residual swing on both sides of the comparison.The additional unit accommodates the integer floor in the decision threshold.Source: §8.1.9 · p. 56

8.2 The “if” proof

• A source solution yields an AWET schedule of cost at most B by choosing coded block orientations and placing the anchor early.These choices make every prefix equation exact, so the prefix penalty is zero; the residual bound and integer threshold then establish feasibility.Source: §8.2 · p. 56

8.3 The “only if” proof

• Any schedule of cost at most B can be made canonical without increasing cost, and its anchor must be early.A tardy anchor would incur a self-term exceeding the explicit feasible benchmark.Source: §8.3 · pp. 56–57
• With an early anchor, every block is coded and determines a unique logical spin and selection variable.The block load is forced to its target value βv.Source: §8.3 · p. 57
• A failed prefix equation would incur at least one unit of squared error, contradicting the assumed cost bound; therefore all prefix equations are exact.The contradiction follows from the master identity, residual lower bound, and decision threshold.Source: §8.3 · p. 57
• The reduction interface pairs source solutions with canonical schedules having an early anchor, one coded state per block, and zero prefix error.Every threshold-feasible schedule can be replaced without higher cost by one with these properties, and every source solution constructs such a schedule.Source: §8.3 · p. 59

9 Polynomial and unary bounds

• The reduction runs in polynomial time and produces numerically polynomially bounded values, establishing strong NP-completeness.The proof composes the polynomial reduction from RXC3 through RPE to AWET and establishes membership in NP.Source: §9 · pp. 59, 63
• Every integer in the constructed AWET instance is below N^650, with an exponent independent of the source instance.The construction has O(N) jobs and unary output length O(N^651), giving the required strong-reduction bound.Source: §9 · p. 62
• The construction computes its quantities with polynomially many arithmetic operations and examines O(n^2) job pairs, while unary output remains polynomial in n.The output contains O(N) integers, each at most N^650.Source: §9 · p. 62

10 Concluding remarks

• The boundary-date result resolves the strong-complexity question, and the reduction uses eight state jobs per source set plus one global anchor.The authors state that the hardness is not caused by a large number of jobs.Source: §10 · p. 63
• A profile-and-gap compiler uses local arithmetic signatures, separated signal intervals, and a positive-definite global penalty to enforce local loads.The authors identify this pattern as potentially useful when a pairwise minimum kernel has one-dimensional signed profiles.Source: §10 · p. 63

Threshold Rounding

• For unrestricted AWET, an anchored semidefinite relaxation and deterministic marginal thresholding yield a polynomial-time universal constant-factor guarantee.Early pairs are charged locally, while tardy costs use a positive-semidefinite minimum-kernel matrix.Source: Threshold Rounding · p. 65, Introduction and overview · p. 66

Introduction and overview

• The approximation is constructive: it specifies the SDP, deterministic rounding, schedule recovery, and finite precision for polynomial running time.The method addresses unrelated earliness and tardiness weight systems, unlike the cited structured-setting FPTAS results.Source: Introduction and overview · p. 66

11 Problem definition and main theorem

• For every ε > 0, the main theorem gives unrestricted AWET a polynomial-time approximation guarantee.The cited theorem passage does not include the factor in the supplied text.Source: §11 · p. 67

12 Canonical side assignment

• An optimal schedule can be chosen in compact V-shaped form, with early jobs ordered by nonincreasing earliness ratio outward from the due date and tardy jobs by nonincreasing tardiness ratio.Every nonempty early set defines a feasible canonical schedule, and minimizing its associated objective gives OPT.Source: §12 · pp. 68–69

13 Why one early anchor is enumerated; 14 The anchored semidefinite relaxation

• Enumerating early-job anchors and solving an anchored SDP preserves the optimum lower bound for a correct anchor while encoding partition costs with pseudo-marginals.If an optimal early set contains the anchor, its integral partition is feasible in the relaxation, so the relaxation optimum is at most OPT.Source: §14 · p. 71

15 Deterministic threshold rounding

• Threshold rounding selects jobs with early marginal at least θ, and the anchor's unit early marginal guarantees the rounded early set is nonempty.The rounding theorem applies θ = 1 − δ for δ ∈ (0, 1/2).Source: §15 · p. 72, §18 · p. 76

16 Charging the early side

• A threshold above 1/2 lets early-pair costs be charged using positive pseudo-joint early mass for pairs rounded early.At θ = 1/2, two jobs can each have marginal 1/2 while their joint-early mass is zero.Source: §16 · pp. 72–73

17.1 The completed tardy kernel

• The completed tardy minimum kernel is positive semidefinite and entrywise nonnegative.Its diagonal entries are the tardy self-costs needed to form the kernel.Source: §17.1 · pp. 73–74

17.2 Covariance domination

• The SDP joint-tardy matrix dominates the outer product of tardy marginals in positive-semidefinite order, though not necessarily entrywise.The difference between the joint-tardy matrix and the rank-one product is a Gram matrix.Source: §17.2 · p. 74

17.3 The payment inequality

• A trace inequality uses the tardy kernel and covariance domination to charge all rounded tardy pairs globally, without a vertex-degree factor.Tardy self-cost also bounds individual tardy-job costs when their tardy marginals exceed the threshold complement.Source: §17.3 · p. 75

18 Approximation ratio and threshold optimization

• The exact-SDP rounding theorem bounds every rounded set, and optimizing the threshold while enumerating anchors yields the optimized exact-SDP approximation factor.For an anchor in an optimal early set, the rounding bound transfers to OPT; choosing the cheapest result across anchors preserves that guarantee.Source: §18 · pp. 76–77

19 Finite precision and polynomial running time

• Finite-precision SDP computation is made exact by reducing the anchor face, finding a rational near-optimal point, and repairing feasibility residuals within reserved objective tolerance.The exact rational realization is computable in time polynomial in binary input length and log(1/α).Source: §19 · pp. 77–79
• A rational convex mixture with an interior point restores exact SDP feasibility after weak optimization, while consuming only the prescribed additive tolerance.Threshold comparisons are then exact rational comparisons, and the resulting schedule is evaluated using the original integer objective.Source: §19 · pp. 82, 84
• Theorem II.21 gives a polynomial-time Turing-model approximation guarantee for every positive rational ε.The proof uses rational threshold selection and polynomial-precision SDP optimization.Source: §19 · p. 83
• For an anchor in an optimal early set, the realization lemma yields an exactly feasible rational point of value at most OPT + α.The rounding inequalities apply to every feasible SDP point, supporting the theorem’s approximation bound.Source: §19 · p. 83

20 Algorithm and implementation details

• The algorithm is feasible and runs in polynomial time; coefficient construction takes O(n^2) arithmetic operations, and it uses n SDPs, each with an order-(n+1) matrix and O(n^2) linear constraints.Source: §20 · pp. 84–85

21 Worked example

• The worked example uses a feasible convex mixture of integral partitions—not an SDP optimum—so its threshold-rounding comparison illustrates mechanics rather than the algorithm’s worst-case guarantee.For the six-job instance, the rounded schedule costs 229 while the unique optimum costs 102; the example explicitly warns that this comparison is not the algorithm’s worst-case certificate.Source: §21 · p. 85, The SDP accounts A, B, U, and L · p. 90, The optimal solution and its cost · p. 92

22.1 Early pairs use local consistency

• A threshold above one half bounds early-pair costs using local joint consistency, without requiring positive semidefiniteness of the early kernel.The early estimate uses eij = ei+ej−1+tij and tij ≥ 0; the threshold supplies the missing early diagonal.Source: §22.1 · p. 93, §23 · p. 94

22.3 The rounding is deterministic

• The rounding is deterministic: a common marginal threshold avoids the linear-versus-quadratic mismatch that can undermine root-relative hyperplane rounding on unary tardiness costs.The anchor ensures the rounded early set is nonempty; enumerating every job guarantees an anchor belongs to the optimal early set.Source: §22.3 · p. 93, §22.4 · p. 93

22.2 Tardy pairs use the kernel diagonal

• Tardy self-costs complete the tardy minimum kernel into a positive-semidefinite matrix, allowing SDP covariance to pay globally for rounded tardy pairs.This global bound handles cases where rounded-tardy jobs have zero pseudo-joint mass but positive actual pair cost.Source: §22.2 · p. 93, The optimal solution and its cost · p. 93, §23 · p. 94

23 Concluding remarks

• The concluding synthesis uses the model’s asymmetry: local consistency pays for early pairs, while the completed tardy kernel and covariance bound pay for tardy pairs.The section also highlights a reusable principle: unary or self-costs can help when diagonal completion makes pair costs positive semidefinite, rather than acting only as a nuisance.Source: §22.4 · p. 93, §23 · p. 94

Weak NP-Completeness at Exact Reversal

• Strict antithetical AWET is weakly NP-complete and admits an exact pseudopolynomial algorithm based on a two-resource recurrence.Binary positional tags encode an exact half-load target, while an anchor turns the dominant scheduling contribution into a completed load square.Source: Weak NP-Completeness at Exact Reversal · p. 95

24 Introduction to the antithetical theorem

• With strict opposite Smith-ratio orders, every nonempty early set defines a canonical schedule, and the optimum is the minimum canonical cost over those sets.The Partition construction encodes an exact half-load condition and uses an anchor to supply a linear field while forcing it early.Source: §24 · pp. 96–97

25 Antithetical hardness: proof architecture

• The Partition reduction maps a subset summing B to tagged load Q/2, eliminating the dominant square; any schedule at threshold has a canonical optimum with the anchor early and load Q/2.The construction outputs a positive-integer AWET instance with strict reversed ratio orders.Source: §25 · pp. 98–99

26 Reduction roadmap

• Binary positional pair tags enforce one choice per source pair while preserving the partition equation; tagged processing times have opposing affine ratio orders, and a final anchor creates a linear field and strict gap between S = Q/2 and other integer loads.Source: §26 · p. 99

27 A distinct half-sum compiler

• From Partition, binary pair tags produce a strictly increasing sequence whose half-sum subsets choose exactly one number per pair and encode a source subset summing to B.The source-to-tagged-instance equivalence holds for even-total inputs; odd totals map to a fixed strict-antithetical no-instance.Source: §27 · pp. 100, 101, 103

28 The strict antithetical scheduling instance

• The scheduling construction uses positive integer data and distinct processing times, with variable-job earliness ratios strictly increasing and tardiness ratios strictly decreasing, both beyond the anchor.The resulting orders are r1 < … < rN < rg and s1 > … > sN > sg.Source: §28 · p. 104

29 The exact equal-load square

• With the anchor early, the exact cost identity expands the canonical cost as a quadratic in side bits and groups dominant terms by aggregate load S, leaving job-specific dependence in residual Ψ.The proof identifies linear and pair coefficients using finite differences.Source: §29 · p. 106
• The exact objective separates into a load square and a bounded residual: Φ = C − DMQ^2/4 + DM(S − Q/2)^2 + DΨ, with |Ψ| ≤ U.The unit integer load gap and M > 2U enable the anchor-forcing and yes/no separation argument.Source: §29 · p. 113

30 Forcing the anchor and separating yes from no

• The reduction is correct: a schedule of cost at most K exists exactly for yes-instances of Partition, with every such canonical optimum placing the anchor early and attaining tagged load Q/2.Binary tagging then decodes the load to a source subset of sum B.Source: §30 · pp. 113, 115, 116
• For strict reverse ratio orders, a two-resource dynamic program computes the exact optimum pseudopolynomially, using O((WE + 1)(P + 1)) rolling memory and permitting schedule recovery.Its states track accumulated earliness weight and processing load; predecessor storage recovers an optimal early set.Source: §30 · pp. 117–118
• Positive-integer AWET remains NP-complete under strict antithetical ratio orders, but its pseudopolynomial algorithm makes this restriction weakly NP-complete.The reduction from Partition establishes NP-hardness, while a canonical schedule is a polynomially checkable certificate.Source: §30 · pp. 118–119
• Strict antithetical positive-integer AWET admits an FPTAS because its induced reverse permutation is separable, so the separating-tree FPTAS applies.The ratio permutation is n(n − 1) · · · 1, an iterated skew sum of singleton permutations.Source: §30 · p. 119

31.1 A “yes” instance

• The two listed vectors each have load 263, with the first explicitly equal to Q/2; the reverse implication recovers a genuine source witness rather than merely a numerically balanced tagged load.Source: §31.1 · pp. 121, 126

31.1 A “yes” instance; 31.2 A similar “no” instance

• In the yes-instance the half-load minimizes the dominant square and falls below threshold; in the no-instance the nearest loads miss the minimum and exceed threshold.The no-instance's closest pair-respecting loads are 293 and 295, one unit from 294.Source: §31.1 · pp. 124–125, §31.2 · pp. 130–131

31.2 A similar “no” instance

• Changing the final source number from 8 to 10 leaves no subset summing to 9, so tagged half-load 294 is absent and the required source equation is impossible.A hypothetical threshold-feasible schedule would force z1 + 2z2 + 5z3 + 10z4 = 9, which has no binary solution.Source: §31.2 · pp. 128, 130
• The exhaustive sixteen-row source audit contains no subset sum 9; therefore, the target instance has no schedule of cost at most K.Source: §31.2 · p. 131
• The 256-vector audit finds the global minimum among anchor-early assignments, while the uniform theoretical lower gap already excludes every non-half load.The numerical audit shows the actual best no-instance cost exceeds K by substantially more than the proof requires.Source: §31.2 · pp. 131–132
• Replacing the last source item 8 with 10 changes the target from 8 to 9, separating two tagged half-load assignments in the yes-instance from nearest no-instance loads Q/2 ± 1.The yes-instance has low-order solutions 1 + 2 + 5 = 8 and 8 = 8; in the no-instance, the square term costs at least one unit of DM and the residual cannot erase the gap.Source: §31.2 · p. 132
• A dominant convex square and a uniform bound on identity-dependent residuals can isolate a hard binary choice using an integral unit gap and a sufficiently large scale.The scale must exceed twice the residual budget, even when the residual’s detailed form is complicated.Source: §31.2 · p. 132

34 Local side assignments and the four signature coordinates

• Each tree node’s block assignment is summarized by early and tardy processing loads and side-specific early and tardy weights.These four coordinates are nonnegative and additive, representing zero tardy load exactly and avoiding subtraction in the recurrence and trimming proof.Source: An FPTAS for Separable Ratio… · p. 133, §34 · p. 138

35 Cross costs and exact bilinear convolution

• At each direct or skew split, cross-block pair costs form an exact nonnegative bilinear expression in the children’s signatures.The separating-tree orientation fixes the ratio-order relation across the two child blocks.Source: An FPTAS for Separable Ratio… · p. 133, §35 · pp. 139–140

An FPTAS for Separable Ratio Permutations

• For fixed total ratio-order refinements whose ratio permutation is separable, AWET admits an FPTAS using coordinated geometric trimming.The method keeps one least-cost representative per four-dimensional box; separability is sufficient, not shown necessary, and the tree may be unbalanced.Source: An FPTAS for Separable Ratio… · p. 133, §32 · p. 134, §33 · p. 137

32 Introduction and proof map

• The exact recurrence enumerates side assignments through a four-coordinate interface; geometric trimming keeps one candidate per box and preserves zero coordinates exactly.Nonnegativity and bilinearity let the multiplicative loss be charged by separating-tree height.Source: §32 · p. 134

33 Ratio-order costs and separable permutations

• The algorithm requires fixed total ratio-order refinements and a separable ratio permutation; equal ratios are allowed, and the separating tree need not be supplied.The tree can be recognized and recovered in linear time; separability is a sufficient structural hypothesis, not a proved necessity for an FPTAS.Source: §33 · p. 137

36 The exact pseudopolynomial dynamic program

• The exact separating-tree recurrence reconstructs an optimal assignment and canonical schedule, and its numerical state count is pseudopolynomial.At the root, the minimum table value equals the optimum of the original scheduling instance.Source: §32 · p. 134, §36 · p. 142
• The exact separating-tree recurrence finds an optimal nonempty early set and reconstructs its canonical schedule in pseudopolynomial time.The root minimizes over states with e > 0; the state space has coordinates bounded by P, WE, and WL, and the direct implementation uses O(nS^2) exact-arithmetic operations.Source: §36 · pp. 143–144

37 Geometric trimming of the exact recurrence

• For separable ratio permutations, geometric trimming returns a schedule costing at most (1 + ε) OPT in time polynomial in the input length and 1/ε.The trimmed recurrence preserves zero patterns, with coordinate inflation at most λ^h and cost inflation at most λ^(2h); at the root, λ^(2H) ≤ 1 + ε.Source: §37 · pp. 147–149

38.1 Instance and ratio orders

• The instance has six jobs and four processing-time values, and its separable ratio permutation has two direct three-job blocks beneath a skew root.The four-coordinate signature retains processing and side-specific weight information needed to price future direct or skew interactions.Source: §38 · p. 150, §38.1 · p. 151, §38.10 · p. 158

38.3 The left block A: trimming actually deletes states

• At block A, trimming compresses eight exact candidates to five and removes a locally competitive state that belongs to the global optimum.The discarded state’s local-cost advantage is outweighed by a larger skew-root interaction.Source: §38.3 · p. 153, §38.10 · p. 158

38.5 Root convolution and the returned solution

• At the skew root, the five retained A states and eight B states produce 40 candidates, trimmed to 35; the least-cost retained solution has early set {3, 5, 6} and cost 4530.All eight exact side assignments in B survive trimming for this parameter.Source: §38.4 · p. 154, §38.5 · p. 155

38.6 What was lost by trimming

• Discarding the exact-optimal path raises the root interaction by 28, producing a net loss of 27 in the final cost.The retained state is locally cheaper by 1, but its larger early-weight coordinate increases the skew-root interaction.Source: §38.6 · p. 156, §38.10 · p. 158

38.7 Exact optimum for comparison

• The trimmed dynamic program returns the least-cost retained feasible root candidate, costing 4530, with bE = {3, 5, 6}; this six-job example is genuinely approximate rather than accidentally exact.Source: §38.5 · p. 155, §38.7 · p. 156

38.8 Canonical schedules and direct cost checks

• Canonical schedules for both the exact optimum and returned set have early load 8, start at time 4, and complete early jobs at times 5, 8, and 12, independently checking the root-DP calculations.The common due date is 12.Source: §38.8 · p. 157

38.9 Approximation-factor audit and effect of tighter trimming

• The theorem guarantees cost at most 1.5 OPT, and a tighter geometric grid preserves the exact-optimal state and returns the exact optimum 4503 on this instance.The ε = 0.50 run demonstrates trimming loss, while the tighter run restores the optimum.Source: §38.9 · p. 158

41 Synthesis by obstacle, certificate, and control

• Global certificates suit aggregate control, while recursive decompositions call for bounded interfaces that capture interactions with the unprocessed tree.The passage identifies the load lock, covariance inequality, and completed square as global certificates; Part IV's interface stores information needed to price cross-interactions.Source: §41 · p. 163

42 Methodological, modeling, and implementation implications

• Canonicalize the schedule first, then inspect ratio orders and separability to select among separating-tree methods, anchored SDP, or available exact methods.The suggested workflow uses exact cross-multiplication with deterministic tie refinements; it is not a claim that nonseparable instances lack stronger algorithms.Source: §42 · p. 164

43 Named open problems and first milestones

• Open problems ask whether unrestricted AWET has a PTAS, whether its approximation factor can improve, which nonseparable orders admit FPTASs, and how to accelerate certified methods.Proposed milestones include bounded-core analysis, coupled rounding bounds, handling a bounded-size prime node, and anchor screening with reachable signature boxes.Source: §43 · p. 165

44 Final perspective

• General positive-integer AWET is strongly NP-complete yet has a constant-factor approximation; exact reversal is weakly NP-complete and admits pseudopolynomial and FPTAS algorithms.The decisive distinction is whether quadratic interactions can be controlled by a dominant certificate or compressed into a bounded constructive interface.Source: §44 · p. 166

A Algebra of the canonical objective

• The appendix separates early-indicator and tardiness-offset expansions to track where constants, linear terms, and quadratic terms enter the objective.It states that the common tardiness offset changes only one block's field on the coded manifold.Source: A Algebra of the canonical objective · p. 167

A.1 Baseline early field

• Collecting the physical early-objective terms assigns them to constants, fields, or couplings; a common tardiness offset changes the logical field by −ηvDv/4.The offset’s cross-block tardy contribution is independent of σ.Source: §A.1 · p. 167, §A.2 · p. 167

B.1 A “yes” instance

• The six-element yes-instance has 48 state jobs and one anchor, and its printed integer data provide a reproducibility certificate for the reduction.The certificate checks no-carry arithmetic, pair synchronization, strict ratio separation, the load lock, the master identity, the threshold, and decoding.Source: §B.1 · p. 168, B Two worked examples · p. 168

B.1.1 The restricted exact-cover instance

• The six-element RXC3 instance is valid and has the unique exact cover S1 and S5.An exact cover must use two sets, and the only disjoint pair is S1 and S5.Source: §B.1.1 · p. 170

B.1.2 The associated prefix-exactness instance

• Substitution of (B.2) gives prefix counts (C1, ..., C6) = (1, 2, 3, 4, 5, 6); successive differences recover the six element-row equations of (B.1), the original incidence rows.Source: §B.1.2 · pp. 171–172

B.1.3 Numerical scales and base processing values

• The scale relationships ensure T dominates block-level M terms, while the ratio-space gap GM dominates block-field variation.The passage states the latter variation is on the order of N^2T.Source: §B.1.3 · p. 172

B.1.4 The 48 state jobs and arithmetic synchronization

• Each block’s eight state jobs have exactly two balanced orientations, enforced by scale-separated arithmetic synchronization.The two zero-load sign vectors are complements; the scale inequalities force the pair and element imbalances to vanish before the residual equation fixes the state.Source: §B.1.4 · p. 175

B.1.5 Kernel data, early ratios, and effective atoms

• The 24 compressed atoms assign mass +1 to occurrences and −3 to controllers, and their effective-ratio bands are strictly ordered R1 > R2 > R3 > R4 > R5 > R6 > R0.The narrowest main gap is Δ4.Source: §B.1.5 · pp. 178, 181
• In this instance, every gap is roughly six orders of magnitude longer than the sum of all within-band widths.Source: §B.1.5 · p. 183

B.1.6 Cross-block couplings and logical-field correction

• Cross-block coefficient differences are within-band residuals, and the field-correction residuals satisfy |ev| ≤ Dv/8.The cross-block residual uses the uniform profile bound |Fv| ≤ 3; the field-correction check is |4ev| ≤ Dv/2.Source: §B.1.6 · p. 186

B.1.7 The load-lock scale, anchor, and due date

• Any wrong integer load costs at least H, exceeding the combined improvement from non-dominant terms, and the anchor cannot be tardy.State-job tardiness ratios si = HLv + ηv are positive and decrease strictly by block; the common due date is the total processing time of 49 jobs.Source: §B.1.7 · p. 189

B.1.8 The constructed 49-job instance

• Within each block, jobs share a tardiness ratio while their early ratios vary with processing time; the anchor is checked using its specified ratios and processing time.The verification rule computes r_j = f_v + λ_v p_j and s_j = H L_v + η_v within each block, with anchor checks p_a = H, r_a = 1 + max r_j, and s_a = 2.Source: §B.1.8 · pp. 191–192
• The 49-job instance is listed through metadata, processing times, and early/tardiness ratios, alongside a separate table of actual integer weights.The decision instance also includes a due date and threshold; the construction ratios are aids, not additional scheduling inputs.Source: §B.1.8 · pp. 190–191, Table 16 · p. 192
• The physical positive-integer input triples can be audited by multiplying each processing time by its corresponding ratio to recover the early and late weights.The row-wise equality wE_j = p_j r_j is stated explicitly; the physical-input verification also refers to the ratios in Table 16.Source: §B.1.8 · pp. 191, 197
• Appendix B labels this material a “yes” instance, followed by long numeric strings without visible job-data labels.The supplied text does not support identifying individual jobs, parameters, or a schedule from these strings.Source: §B.1.8 · pp. 200–201

B.1.9 The master identity and decision threshold

• A positive margin separates the least main penalty for a nonzero integer prefix error from residual terms that can favor either decision state and the integer floor.The comparison accounts for a Γ advantage for the yes-state, another Γ for the no-state, and one full unit for the integer floor.Source: §B.1.9 · p. 204

B.1.10 The “if” case: constructing and evaluating the schedule

• The exact-cover assignment yields 24 early state jobs, 24 tardy state jobs, and an early anchor; zero prefix penalty certifies the constructed AWET instance as a yes-instance.Every block has tardy load βv.Source: §B.1.10 · p. 205
• Each row’s completion is start plus processing time; its deviation is measured from d on the appropriate side, and consecutive rows verify compactness.The listed rows also show the corresponding cost contribution obtained by multiplying deviation by the relevant weight.Source: §B.1.10 · pp. 212, 215, 216

• The reverse enforcement specializes through anchor, load, and prefix gates: tardiness violates the anchor bound, nonzero integer load error incurs dominant loss, and non-prefix-exactness creates a nonzero integer residual.Source: §B.1.11 · p. 216
• Every optimal block has load βv, and the synchronization calculation restricts it to one of two coded states.Source: §B.1.11 · p. 216
• A schedule meeting the bound must be prefix-exact, and successive differences then make its selected subset-columns an exact cover.Source: §B.1.11 · p. 216
• The exhaustive audit finds one prefix-exact row; the closest non-prefix-exact state has one unit of prefix error but still exceeds B by an enormous margin.Source: §B.1.11 · p. 217

B.1.12 How to reproduce the numerical audit

• The audit can be regenerated with exact integer and rational arithmetic by constructing the incidence and kernel data, deriving atom bands and objective coefficients, then checking all 64 coded vectors.Source: §B.1.12 · p. 223

B.2 A “no” instance

• A degree-preserving 2-switch exchanges elements between two subset-columns while retaining three elements per column and three occurrences per element, destroying the prior unique cover.Source: §B.2 · p. 224

B.2.1 The modified restricted exact-cover instance

• Every pair of subset-columns intersects, so no two-column exact cover exists; the modified restricted exact-cover instance is therefore a no-instance.Source: §B.2.1 · p. 225

B.2.2 Prefix data and an exhaustive source-level audit

• The closest candidate x† = (1, 0, 0, 0, 1, 0) has a single error at the third prefix, and exhaustive checking finds no prefix-exact two-column candidate.Source: §B.2.2 · p. 228

B.2.3 The numerical compiler for the no-instance

• The narrowest main gap, b∆3, is charged to that failed prefix; the minimum-kernel data also show a transfer from block 1 to 3 cancels in f3 through f6.Source: §B.2.3 · p. 231

B.2.4 Load lock, anchor, and the 49-job no-instance

• The strict-dominance certificate rules out placing the anchor tardy in any optimal canonical assignment.The section identifies a strict dominance certificate and states this consequence explicitly.Source: §B.2.4 · pp. 239–240
• The no-instance construction lists ratio-level data and integer job inputs for all 49 jobs.The tables record construction ratios and each job’s metadata, processing time, and early/tardiness penalties.Source: §B.2.4 · pp. 240–241, Table 27 · p. 241
• The 49-job no-instance is given as physical positive-integer job triples, with verification by multiplying each p_j by its Table 27 ratios and checking rowwise equality.The passage cautions that the certificate is rowwise equality, not visual digit matching.Source: §B.2.4 · p. 246, Table 28 · p. 246
• The visible appendix headers identify B.2 as a “no” instance, while the accompanying text does not expose a readable construction or verification.Source: §B.2.4 · p. 250

B.2.5 Master identity and decision threshold for the no-instance

• The master decomposition retains its form for a coded state x ∈{0, 1}6.The passage introduces the coded state but does not provide the remainder of the decomposition.Source: §B.2.5 · p. 253
• The exact objective constant includes within-band and rounding effects in bR, with no asymptotic term hidden in (B.5).The passage identifies the constant but does not expose its value.Source: §B.2.5 · p. 253
• A nonzero integer prefix error costs more than the most favorable possible residual swing on either side of the threshold comparison.This gap makes the attempted forward construction fail and the reverse supposition contradictory.Source: §B.2.5 · p. 254

B.2.6 The “if” route: where the forward construction fails

• The former cover’s coded state satisfies every block and load gadget, but uncovered e3 creates a one-unit third-prefix error that pushes its cost above the threshold.Even the least expensive coded assignment remains above the threshold, and exhaustive enumeration confirms that all 64 coded states have positive cost difference.Source: §B.2.6 · pp. 255, 256, 261, Table 29 · p. 257

B.2.7 The “only if” route: the hypothetical target witness is impossible

• A schedule within the target cost must keep the anchor early, have target loads and one of two coded states in each block, and satisfy every prefix equation—conditions that force an impossible exact cover.The load-lock loss excludes block-load errors; the resulting binary vector would select exactly two columns, but every pair of columns intersects.Source: §B.2.7 · pp. 261–262

B.2.8 Side-by-side conclusion

• The two examples differ only by exchanging e3 and e4 between columns S1 and S3, and the reduction records that local combinatorial change exactly.Source: §B.2.8 · p. 263, Table 30 · p. 263
• A yes-instance reaches the decision bound by annihilating every prefix square; in a no-instance, reaching it would force an exact cover forbidden by the source incidence matrix.The nearest analogous no-instance assignment incurs one third-prefix square.Source: §B.2.8 · p. 263