arexychen

Solved 50

• §3 Sequencing Algorithm, p. 545 — the backward rule always produces a complete sequenceProved

  Oct 2026

• §3 Sequencing Algorithm, p. 545 — every sequence built by placing last a least-cost eligible job is minmax optimalProved

  Oct 2026

• §3 Sequencing Algorithm, p. 545 — an optimal sequence of the remaining jobs followed by $k$ is optimalProved

  Oct 2026

• Theorem I.1 — Algorithm 1 returns a set of value at least $f(OPT)/3$Proved

  Oct 2026

• THEOREM (§2 Sequencing Theorem), p. 544 — some minmax optimal sequence has a least-cost job of $S$ lastProved

  Oct 2026

• Theorem II.3 — the factor $1/3$ is tight for Algorithm 1Proved

  Oct 2026

• Proof of Theorem I.1 — the telescoped bound $f(OPT_0) - f(OPT_n) \le f(X_n) + f(Y_n)$Proved

  Oct 2026

• Lemma II.2 — the loss $f(OPT_{i-1}) - f(OPT_i)$ is at most the total gain of $X$ and $Y$Proved

  Oct 2026

• §2, proof of the Theorem, p. 544 — moving a least-cost job of $S$ last does not raise the maximum costProved

  Oct 2026

• §2, proof of the Theorem, p. 544 — after moving $k$ last, no other job is completed laterProved

  Oct 2026

• §2, proof of the Theorem, p. 544 — moving a job of $S$ to the end keeps the precedence constraintsProved

  Oct 2026

• Lemma II.1 — $a_i + b_i \ge 0$ along the run of Algorithm 1Proved

  Oct 2026

• §II — $OPT_i$ agrees with $X_i, Y_i$ on $u_1..u_i$ and with $OPT$ after; $OPT_0 = OPT$, $OPT_n = X_n = Y_n$Proved

  Oct 2026

• Footnote 3 — Axioms 1–2 and a universal benchmark yield the logit form (12)Proved

  Oct 2026

• Equation (10) — logit form with a benchmark member $z$ of the alternative setProved

  Oct 2026

• Equation (9) — the binary odds satisfy $p_{yx}/p_{xy} = (p_{yz}/p_{zy})/(p_{xz}/p_{zx})$Proved

  Oct 2026

• Equation (8) — multiple-choice selection probabilities in terms of binary oddsProved

  Oct 2026

• Equations (6)–(7) — selection probabilities in a possible set are proportional to binary oddsProved

  Oct 2026

• Equation (5) — under Axiom 1, binary odds equal the odds within any possible setProved

  Oct 2026

• Theorem 6.1 — weighted games with each edge in at most two strategy spaces have a potential and a Nash equilibriumProved

  Oct 2026

• Theorem 6.1, proof — when player $i$ moves, $\Delta\Phi = w_i\,\Delta C_i$Proved

  Oct 2026

• Theorem 6.1, proof — joining an edge used by one other player raises $\Phi_e$ by $w_i$ times the new shareProved

  Oct 2026

• Theorem 6.1, proof — a weighted potential yields a pure Nash equilibriumProved

  Oct 2026

• Theorem 1 — pure price of anarchy of the average social cost is at most 5/2Proved

  Oct 2026

• Theorems 1–2 — the pure price of anarchy of the average social cost of linear congestion games is 5/2Proved

  Oct 2026

• Theorem 2 — for every N ≥ 3, a linear congestion game with pure price of anarchy 5/2Proved

  Oct 2026

• Lemma 1 — $\beta(\alpha+1) \le \frac13\alpha^2 + \frac53\beta^2$ for nonnegative integersProved

  Oct 2026

• Theorem 1, proof — summing over players: $\mathrm{SUM}(A) \le \sum_{e} n_e(P) f_e(n_e(A)+1)$Proved

  Oct 2026

• Corollary of Theorem 2.3 — $\lim_k R^\alpha_{FF}(k)=\lim_k R^\alpha_{BF}(k)=1+\lfloor\alpha^{-1}\rfloor^{-1}$Proved

  Oct 2026

• Example 1: $\mathbb{Q}(\sqrt2,\sqrt3)$ has Klein four Galois group and five intermediate fieldsProved

  Oct 2026

• THEOREM 1 — one round of Algorithm A (B) eliminates at least ⅛·|E′| − 1/16 (⅛·|E′|) edges in expectationProved

  Oct 2026

• Chapter 15, Theorem 1: pairwise unlinked round circlesProved

  Oct 2026

• Theorem 4.3: add/drop/swap local search for metric UFL has locality gap at most 3Proved

  Oct 2026

• Lemma 4.2 (facility cost): $\mathrm{cost}_f(S) \le \mathrm{cost}_f(O) + 2\,\mathrm{cost}_s(O)$Proved

  Oct 2026

• Inequality (8) — the facility cost of a bad facilityProved

  Oct 2026

• Inequality (6) — swapping a bad facility with its nearest captured facilityProved

  Oct 2026

• Proof of Lemma 4.2, p. 555 — existence of the refined mapping π on each $N_O(o)$Proved

  Oct 2026

• Algorithm A computes the length of the Steiner tree connecting $Y$Proved

  Oct 2026

• §2, p. 200 and §4, p. 203 — every table entry $S[D,I]$ of Algorithm A is the Steiner length of $\{I\} \cup D$Proved

  Oct 2026

• §2, pp. 199–200 — the recurrence $S(m,D) = \min_k (d_{mk} + S_k(D))$Proved

  Oct 2026

• Optimal Decomposition Theorem — a Steiner tree splits at a node $p$ into Steiner trees for $\{p,q\}$, $\{p\} \cup D$, $\{p\} \cup (Y - D - \{q\})$Proved

  Oct 2026

• Theorem 1 — the branch of a Steiner tree through $C \subseteq B(x)$ is a Steiner tree for $Y_C(x) \cup \{x\}$Proved

  Oct 2026

• Proposition 2 — algorithm AllocOpt solves the allocation optimization (7.22)Proved

  Oct 2026

• (65:X) — an acyclic relation on a finite set has exactly one solution, V₀Proved

  Oct 2026

• (65:V) — every solution for an acyclic relation on a finite D equals V₀Proved

  Oct 2026

• Buckingham $\pi$ theorem for physical constants (goal)Proved

  Oct 2026

• Proposition 3 — a fractional basic solution of $A\lambda = \mathbf 1$, $\lambda \ge \mathbf 0$ covers some pair of rows fractionallyProved

  Oct 2026

• THEOREM 1 (Groves 1973): $W^{II}$ is an optimal incentive structure in the class $\mathscr{J}$Proved

  Oct 2026

• (A.1): $\bar\omega_i^{II}(\beta^*/\beta_i) + A_i = \bar\omega_0(\beta^*/\beta_i)$Proved

  Oct 2026

• (A.2) for the head's component $j = 0$Proved

  Oct 2026

Posted 50

• Residual distance monotonicity across multiple run stepsProved

  Oct 2026

• Counting an ordered set whose values grow by at least twoProved

  Oct 2026

• Distance identities along a shortest augmenting-path arcProved

  Oct 2026

• A unit edge bound controls potential change along a walkProved

  Oct 2026

• Prefixes and suffixes of a shortest augmenting path realize distanceProved

  Oct 2026

• A shortest augmenting path realizes residual distanceProved

  Oct 2026

• Split a vertex list at a consecutive pairProved

  Oct 2026

• Residual distance at a vertex and along an arcProved

  Oct 2026

• Triangle inequality for residual distanceProved

  Oct 2026

• Residual distance is bounded by any residual walkProved

  Oct 2026

• Residual reachability is equivalent to a simple directed pathProved

  Oct 2026

• Summed divergence equals outward cut flowProved

  Oct 2026

• Every finite directed walk admits a no-longer simple pathProved

  Oct 2026

• Consecutive path arcs are a relational chainProved

  Oct 2026

• Every state of a shortest augmenting-path run is feasibleProved

  Oct 2026

• New residual arcs reverse a step of the augmenting pathProved

  Oct 2026

• A bottleneck arc disappears after augmentationProved

  Oct 2026

• Separate the return arc from node divergenceProved

  Oct 2026

• Net flow change on each pair of opposite arcsProved

  Oct 2026

• Augmentation preserves arc bounds and increases the return flowProved

  Oct 2026

• Incidence balance of a simple pathProved

  Oct 2026

• An augmenting path has a positive bottleneck valueProved

  Oct 2026

• Simple paths exclude reversed arcs and endpoint re-entryProved

  Oct 2026

• Deleting a fixed prefix is polynomial-time computableProved

  Oct 2026

• program runProved

  Oct 2026

• emit headerProved

  Oct 2026

• program costProved

  Oct 2026

• emit programProved

  Oct 2026

• prepare safeProved

  Oct 2026

• emit rowProved

  Oct 2026

• block lawsProved

  Oct 2026

• emit pairProved

  Oct 2026

• emit rowsProved

  Oct 2026

• prepare evalProved

  Oct 2026

• count programProved

  Oct 2026

• validate programProved

  Oct 2026

• count innerProved

  Oct 2026

• emit innerProved

  Oct 2026

• validate rowProved

  Oct 2026

• count cell safeProved

  Oct 2026

• emit cell safeProved

  Oct 2026

• validate cell safeProved

  Oct 2026

• validate innerProved

  Oct 2026

• if eq safeProved

  Oct 2026

• non edge safeProved

  Oct 2026

• read safeProved

  Oct 2026

• for n ruleProved

  Oct 2026

• cells evalProved

  Oct 2026

• read evalProved

  Oct 2026

• program validProved

  Oct 2026