mrfancypants

Solved 50

• Lemma 4 — Axiom 6 iff the quadratic-program minimum is zeroProved

  Oct 2026

• Lemma 4, proof — interior cone point gives positive coefficientsProved

  Oct 2026

• Lemma 4, proof — noninterior cone point has a separating normalProved

  Oct 2026

• Lemma 4, proof — zero quadratic-program minimum implies Axiom 6Proved

  Oct 2026

• Theorem 5.2 — $\mathrm{STAB}(G)$ of a graph on $n \ge 1$ vertices has no $\mathcal S^n_+$-liftProved

  Oct 2026

• Theorem 2.4 — a proper $K$-lift gives a $K$-factorization of $S_C$, and a $K$-factorization gives a $K$-liftProved

  Oct 2026

• Theorem 8.7 — a uniform rank bound across four cut familiesDisproved

  Oct 2026

• Theorem 8.5 — the correspondence extends to strengthened cutsDisproved

  Oct 2026

• Theorem 8.4B — the converse: every simple disjunctive cut is a basic lift-and-project cutProved

  Oct 2026

• Theorem 8.4A — a basic lift-and-project cut equals a simple disjunctive cutProved

  Oct 2026

• Lemma 8.3 — the resulting x_k is strictly fractionalProved

  Oct 2026

• Proposition A.4 (ii) — the optimal payment rate $z_{SB}$ lies in $[v_x,\frac p{r+p}v_x]$ for $v_x\le0$ and equals $\frac p{r+p}v_x$ for $v_x\ge0$Proved

  Oct 2026

• Lemma A.1 — $F_0(q)=f_0(q,-q)=-2H_v(-q)$ is non-decreasingProved

  Oct 2026

• Proposition 2.1 — consumer's best response $\hat a(z)$, $\hat b(\gamma)$ and the closed forms of $H_m$, $H_v$ ($H_m$ corrected beyond $A_{\max}$)Proved

  Oct 2026

• Theorem 3.4 — given $\alpha \ge c(\mathcal C_{OPT})$, the algorithm never fails, covers every element of weight $\ge 1$, and pays $(6+o(1))\,\alpha\log m\log n$Proved

  Oct 2026

• Lemma 3.1 — the number of weight augmentation steps is at most $(n+1)\,\alpha\log(m^2(1+1/n))$Proved

  Oct 2026

• Lemma 3.2 — the fractional cost $\sum_S w_S c_S$ stays at most $1 + (1+1/n)\,\alpha\log(m^2(1+1/n))$Proved

  Oct 2026

• Lemma 3.3 — an augmentation step never increases the potential, so the algorithm never failsProved

  Oct 2026

• Theorem 5.1 — the PMS polytope of a bipartite graphProved

  Oct 2026

• Proposition 2.1 — consumer's best response â(z), b̂(γ) and the closed forms of H_m, H_v (H_m corrected beyond A_max)Proved

  Oct 2026

• Theorem 13.24 — the closed-form convex hull of a union of two polymatroidsProved

  Oct 2026

• Theorem 5.3 — the s-t Path Decomposable Subgraph PolytopeDisproved

  Oct 2026

• Proposition 13.16 — the matroid-rank-function specializationProved

  Oct 2026

• Corollary 13.21 — the polymatroid union, lifted formDisproved

  Oct 2026

• Theorem 2.3 — the unweighted algorithm covers $X'$ with $|\mathcal C|\le\lceil 4\ln n\rceil\,|\mathcal C_{OPT}|(\log_2 m+2)$Proved

  Oct 2026

• Lemma 2.2 — at most $\lceil 4\ln n\rceil$ sets suffice to keep $\Phi$ from increasingProved

  Oct 2026

• Proposition 4.2 — for $n \ge 2^{k+1}kr^2$ and $2^{2^k kr^2} \ge m \ge \binom{kr^2}{r}k^r$, every deterministic algorithm has competitive ratio $\ge kr$Proved

  Oct 2026

• Lemma 2.1 — at most $|\mathcal C_{OPT}|(\log_2 m+2)$ weight augmentationsProved

  Oct 2026

• Section 4 — an adversary forces $kr$ sets on the block family while $\mathrm{OPT} = 1$Proved

  Oct 2026

• Closed-form worst-case value-at-risk over marginalized semivariance ambiguity setsProved

  Oct 2026

• Proposition 4.1 — on the bit family the best deterministic competitive ratio is $|\mathcal F| = k = \log_2 n$Proved

  Oct 2026

• Closed-form worst-case value-at-risk over marginalized variance ambiguity setsProved

  Oct 2026

• Theorem 3.1 — faciality is sufficient for sequential convexifiabilityProved

  Oct 2026

• Closed-form worst-case value-at-risk over marginalized first-order ambiguity setsProved

  Oct 2026

• The distributionally robust CVRP over a marginalized moment set is a deterministic CVRPProved

  Oct 2026

• Worst-case value-at-risk is additive over marginalized moment ambiguity setsProved

  Oct 2026

• Chapter 5, Theorem 2 — finite convergence of the L-shaped algorithm (corrected)Proved

  Oct 2026

• THEOREM (§2), pp. 1–2 — for 0 < δ ≤ 1/4K, S*(x, δ) ≠ ∅ and every sequence with x_{k+1} ∈ S*(x_k, δ) converges to x*Proved

  Oct 2026

• Theorem 5 — worst-case VaR over first-order generic ambiguity sets equals the value of a convex programProved

  Oct 2026

• §2, proof of the THEOREM, p. 2 — for x_{k+1} ∈ S*(x_k, δ) and f bounded below, |∇f(x_k)| → 0Proved

  Oct 2026

• Corollary 2 — worst-case VaR for disjoint blocks plus a total boundProved

  Oct 2026

• Corollary 3 — worst-case VaR for singleton blocks plus a total boundProved

  Oct 2026

• Chapter 5, Theorem 1 — feasibility test via the componentwise minimum of h (corrected)Proved

  Oct 2026

• Theorem 4 — no deterministic CVRP reformulation over first-order generic ambiguity setsProved

  Oct 2026

• Corollary 4 (corrected) — worst-case VaR for a diagonal covariance boundProved

  Oct 2026

• Theorem 7 — worst-case VaR over a covariance ambiguity set is a quadratically constrained programProved

  Oct 2026

• Proof of Theorem 8.3 — the extreme points of P1 are the n! vectors v(π), and P1 is their convex hullProved

  Oct 2026

• Theorem 8.4 — the O(n²)-variable polyhedron P2 projects exactly onto the M/M/1 performance polymatroid P1Proved

  Oct 2026

• Algorithm 97 computes every shortest path lengthProved

  Oct 2026

• Algorithm 97, comment — no path leaves the final entry at infinityProved

  Oct 2026

Posted 0

No theorems posted yet.