Results on configuration programs, competing trees, the encoding and the reduction, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Comparison of the configuration programs — Lemma 1.3. The type configuration value is at most the individual configuration value, which is at most the optimum.
• The counting bound — Lemma 1.4. If every size exceeds 1/6, every configuration has at most five items and LP is at least the number of items divided by 5.
• Unbounded configuration gap (OpenAI) — Theorem 3.1. For every c there is an instance with sizes above 1/6 whose configuration values equal B and whose optimum exceeds B + c.
• Graph-to-packing reduction (OpenAI) — Theorem 4.1. A polynomial-time map from (G, k) to 5B items: a cover of size k gives B bins; B + c bins give a cover of size k + rho n.
• Matching by sorting — Lemma 5.2. If every prefix has at least as many h's as z's, the sorted lists satisfy h_(j) <= z_(j).
• Competing trees (OpenAI) — Lemma 1.1. Two trees with depth quotas: each alone can be hit d times on every root-to-leaf path, but with shared quotas one has an unhit path.
• Coordinate order — Lemma 2.1. One step of position outweighs every earlier edge offset; one step of edge offset outweighs every baseline difference within the edge.
• Geometry of the cells — Lemma 3.1. Nested cells with gaps at least three widths; short intervals meet at most one cell of a depth and at most one job cell.
• Scalar encoding (OpenAI) — Lemma 2.1. Sizes in (1/6, 1); a five-item bin has primary score at most 0, zero exactly for the four patterns; good tuples fit iff their coordinates sum to at most 0.
• Good anchors under an additive allowance (OpenAI) — Lemma 3.1. With at most B + c bins, fewer than K items leave the patterns and fewer than 3K anchors of each label leave good tuples.
• Completion and key inequalities — Lemma 4.1. A good M tuple fits iff the completion meets the deadline; a good G tuple needs a row and a resource not later than its key.
• Completeness (OpenAI) — Proposition 2.1. A vertex cover with at most k vertices gives a packing into B bins.
• Fractional value for K4 (OpenAI) — Proposition 3.1. For K4 and k = 2 both configuration programs have value exactly B.
• Coverage at every test point — Lemma 1.2. In a packing into B + c bins every test point of a vertex lies in at least d - 6K completion intervals.
• A large count on one side (OpenAI) — Lemma 2.1. Every vertex uses at least d - 6K length-one global items on its plus side or on its minus side.
• Long matches at a job (OpenAI) — Lemma 3.1. At a job position that is not excluded, at least d - x_v^+ - 9K keys take long rows of the same position.
• Soundness (OpenAI) — Proposition 4.3. A packing into at most B + c bins yields a vertex cover with at most k + rho n vertices.
• Additive hardness (OpenAI; uses Hastad's theorem) — Theorem 5.2. For fixed c it is NP-hard to distinguish packings into B bins from instances with no packing into B + c bins.
• Additive approximation and P = NP — Corollary 5.3. A polynomial-time algorithm within OPT + C bins exists iff P = NP (the forward direction uses Hastad's theorem).

Reading order

Read the lessons in order; each uses the notation and results of the previous ones.