A New Polynomial-Time Algorithm for Linear Programming
Combinatorica, 1984 · paper · Mathematics and statistics
Presents a new polynomial-time algorithm for linear programming. It repeatedly applies projective transformations followed by optimization over an inscribed sphere, and is stated to run faster than the ellipsoid algorithm by a factor of O(n^1/2) in the worst case.
Checked: PDF from stat.uchicago.edu, fetched 4 Oct 2026. Page numbers are those of that PDF.
13 findings
Substance Theorem 1 ("In O(n(q+log n)) steps the algorithm finds a feasible point x such that cᵀx/cᵀa₀ ≤ 2⁻ᑫ") and Theorem 3 ("There exists a point b′∈B(a₀,αr)∩Ω″ such that f′(b′) ≤ f′(a₀)−δ") are stated without the zero-optimum hypothesis, and the proof of Theorem 3 uses c′ᵀx*=0 ("c′ᵀb′ = (1−λ)c′ᵀa₀+λc′ᵀx* = (1−λ)c′ᵀa₀"), even though the canonical form explicitly allows min cᵀx > 0.
- p. 5 Section 2.1, canonical assumptions
cᵀx ≥ 0 for every x ∈ Ω∩Δ
- p. 7 Theorem 1
cᵀx / cᵀa₀ ≤ 2⁻ᑫ
- p. 9 Theorem 3
f′(b′) ≤ f′(a₀)−δ
- p. 10 Proof of Theorem 3
c′ᵀb′ = (1−λ)c′ᵀa₀+λc′ᵀx* = (1−λ)c′ᵀa₀
Only the authors can say what is right here.
Judge's note: Checked p5 (canonical form: the output may be 'a proof that min{cᵀx | x∈Ω∩Δ} > 0', so a positive optimum is admissible), p7 (Theorem 1, unconditional), p8 (Theorem 2 includes the alternative '(ii) the minimum value … is strictly positive'), p9 (Theorems 3 and 4, unconditional), p10 (the proof of Theorem 3 drops λc′ᵀx*, i.e. it assumes c′ᵀx*=0) and p13 (the proof of Theorem 1 relies on Theorem 2(i) only). Reworked the counterexample myself: n=3, A=(1,−1,0), c=(1,1,1). Aa₀=0, cᵀx≥0 and cᵀa₀=1≠0, so all assumptions hold. The feasible set is x₁=x₂ on the simplex, where cᵀx=1, so cᵀx/cᵀa₀=1>2⁻ᑫ for every q≥1. After the transformation, c′=e/3, so c′ᵀy=1/3 on the simplex and f′(y)=const−Σ ln yⱼ, which is minimised at a₀∈Ω″. No b′ achieves a reduction δ>0, so Theorem 3 is false as printed in this case. Section 2.2 comment 3 ('The target minimum value of the objective function is zero') suggests the hypothesis was intended, but Theorems 1, 3 and 4 do not state it, and Theorem 2 shows the alternative is needed.
Second check: another model agreed
Report a problem with this finding
Substance Lemma 4.2 ("Let β=α√(n/(n−1)). Then for any x∈B(a₀,αr), |Σ ln xⱼ/a₀ⱼ| ≤ β²/2(1−β)") omits the condition β<1 that Lemma 4.1 requires, while Section 3.4 allows any 0<α<1, for which β can exceed 1 and the bound is negative.
- p. 9 Section 3.4, parameter range
0 < α < 1
- p. 11 Lemma 4.2
β = α√(n/(n−1))
- p. 11 Lemma 4.2, asserted bound
|Σⱼ ln(xⱼ/a₀ⱼ)| ≤ β²/[2(1−β)]
Only the authors can say what is right here.
Judge's note: Checked p9 ('0<α<1') and p11 (Lemma 4.1 'If |x|≤β<1'; Lemma 4.2 has no restriction on β, and its proof applies Lemma 4.1). With n=3 and α=0.9: β²=0.81·1.5=1.215, β≈1.1023, and β²/(2(1−β))≈−5.94. At x=a₀ the left side is 0, so the inequality reads 0≤−5.94, which is false. The δ formula in the proof of Theorem 4 (p12) has the same implicit requirement α√(n/(n−1))<1. The recommended α=1/4 is unaffected, but the lemma is false as printed for permitted parameters.
Second check: another model agreed
Report a problem with this finding
Substance Section 5 Step 3: second constraint 'Aᵀu+v+(c−Aᵀu0)λ = c' omits −v0, so the claimed strictly interior feasible point x=x0, y=y0, u=u0, v=v0, λ=1 gives c+v0 ≠ c.
- p. 14 Section 5, Step 3, second constraint
(c−A^T u_0)λ = c
- p. 14 Section 5, Step 3, sentence after the system
is a strictly interior feasible solution
- p. 14 Section 5, Step 3 (artificial variable), second constraint and the 'Note that' sentence
A^T u+v+(c−A^T u0)λ = c
Judge's note: The p.386 image shows (c−Aᵀu0)λ with no v0 term. The text says v0 is strictly interior in the positive orthant, so v0>0. Substituting gives Aᵀu0+v0+c−Aᵀu0 = c+v0. The first constraint is built correctly, carrying +y0. The coefficient should be (c−Aᵀu0−v0). Scalar check: A=1, c=1, u0=1, v0=1.
Second check: another model agreed · checked by hand
Report a problem with this finding
Substance Section 5 Step 3: third constraint 'cᵀx−bᵀu+(−cᵀx0+bᵀv0)λ = 0' has bᵀv0 where bᵀu0 is required for the stated starting point to be feasible.
- p. 14 Section 5, Step 3, third constraint
(−c^T x_0+b^T v_0)λ = 0
- p. 14 Section 5, Step 3, third constraint
c^T x−b^T u+(−c^T x0+b^T v0)λ = 0
Judge's note: The image clearly shows bᵀv0. At (x0,u0,λ=1) the left-hand side is bᵀ(v0−u0), which is not zero in general. v has the dimension of c and b the dimension of the rows of A, so bᵀv0 is also ill-typed when m≠n. Scalar example: c=b=1, x0=1, u0=1, v0=2 gives 1, not 0.
Second check: another model agreed
Report a problem with this finding
Substance Section 5 asserts that T "maps P₊ onto Δ" and that "the inverse image of x′ gives an optimal solution to the original problem", but T(P₊) misses the face x′ₙ₊₁=0. The transformed problem over the closed simplex can attain c′ᵀx′=0 only at x′ₙ₊₁=0, where the inverse xᵢ=aᵢx′ᵢ/x′ₙ₊₁ is undefined.
- p. 14 Section 5, Step 4, property 1
It maps P₊ onto Δ.
- p. 14 Section 5, inverse transformation
xᵢ = aᵢx′ᵢ/x′ₙ₊₁
- p. 15 Section 5, final paragraph
the inverse image of x′ gives an optimal solution to the original problem
Only the authors can say what is right here.
Judge's note: Checked p13–p15. From the printed definition, x′ₙ₊₁=1/(Σxⱼ/aⱼ+1)>0, so the image is not all of Δ. Reworked the counterexample (min x subject to x≥1, −x≥0, x≥0; all starting values 1; Step 3 with the coefficients needed for interior feasibility). The equations are x−y₁+λ=1, −x−y₂+2λ=0, u₁−u₂+v=1, x−u₁=0. These give λ≥max(x/2,1−x)≥1/3, so the original problem is infeasible. Homogenised: x′−y₁′+λ′−t′=0, −x′−y₂′+2λ′=0, u₁′−u₂′+v′−t′=0, x′−u₁′=0. The vector (0,0,0,0,1/2,1/2,0,0) is feasible on the simplex with λ′=0. Conversely, λ′=0 forces x′=y₂′=u₁′=0, then y₁′=t′=0. So every zero-objective point has t′=0 and no inverse image, which contradicts the final paragraph on p15. (Separately, the printed Step 3 coefficients '(c−Aᵀu₀)λ' and '(−cᵀx₀+bᵀv₀)λ' look inconsistent with interior feasibility, but that is outside this cluster.)
Second check: another model agreed
Report a problem with this finding
Reference or label Section 3.3 prints the inverse of T(a, a0) as "x = Dx′ / e^T Dx"; the denominator should be e^T Dx′.
- p. 8 Section 3.3, formula after 'Its inverse is given by'
e^T Dx
- p. 3 Section 1.4, property 1
Its inverse is given by
Judge's note: Enlarged page 8 crop: the numerator x has a clear prime, the denominator x has none. The correct form appears componentwise in Section 1.4 (page 3: x_i = a_i x′_i / Σ a_j x′_j) and in Step 1.5 (page 7: b = Db′ / e^T Db′). As printed, x appears on both sides and the formula is not the inverse. The fix is evident.
Second check: another model agreed
Report a problem with this finding
Reference or label Section 3 opens 'In this Section we show how the computations in step 2 represent an underlying conceptual sequence of operations', but the computations unpacked (b=φ(a): projective transformation, optimisation over ball, inverse transformation) are those of Step 1 in Section 2.3; Step 2 is 'Check for infeasibility'.
- p. 7 Section 3, first sentence
we show how the computations in step 2 represent an underlying
- p. 7 Section 2.3, Step 2
Step 2. Check for infeasibility.
- p. 7 Section 3, first sentence
we show how the computations in step 2 represent an underlying conceptual sequence of operations
- p. 7
In this Section we show how the computations in step 2 represent
Judge's note: Page 6 shows Step 1 'Compute the next point in the sequence' with sub-steps 1-5 (continuing to sub-step 5 on p.7); Step 2 on p.7 only defines the potential and the infeasibility test. Section 3.2 (p.8) describes b=φ(a) as three operations matching Step 1. The pointer should read Step 1.
Second check: another model agreed
Report a problem with this finding
Reference or label Section 6.3 (p. 393): "From equations (22) and (24)" introduces (25) N = O(m√n), which follows from (23) and (24).
- p. 21 Section 6.3, before equation (25)
From equations (22) and (24)
- p. 20 Section 6.3, equation (23)
We use equation (17) to bound the R.H.S. of equation (23)
Judge's note: Viewed pages 20 and 21. (23) is ln√2·N ≤ ∑_i ∑_k |ln Δ_i^(k)| and (24) bounds that same double sum by O(m√n); together they give (25). (22) is the single-term identity |Δδ| = |ln Δ| and does not contain N. The text on p. 392 itself says "We use equation (17) to bound the R.H.S. of equation (23)", confirming (23) is the equation being combined with (24).
Second check: another model agreed
Report a problem with this finding
Wording Theorem 4 states "For α=1/4 we may take δ=1/8" with no condition on n, but the proof shows only "If α=1/4, then lim δ(n)≧1/8" as n→∞; its finite-n remark is "If n≧4, α=1/5 then δ≧1/10".
- p. 9 Theorem 4
For α=1/4 we may take δ=1/8
- p. 12 Proof of Theorem 4, observation 1
then lim δ(n)≧1/8
- p. 12 Proof of Theorem 4, observation 2
then δ≧1/10
- p. 7 Section 2.3, Step 2
For example if α=1/4 then δ=1/8
Only the authors can say what is right here.
Judge's note: Read on the page 9 and page 12 images. The proof defines δ = α − α²/2 − α²n/((n−1)[1 − α√(n/(n−1))]). I checked that this follows from the line above it (β²/(1−β) with β = α√(n/(n−1))). Evaluated at α = 1/4 it gives about 0.1016 at n = 4 and 0.1245 at n = 10, both below 1/8, and first exceeds 1/8 at n = 11 (0.1256). The limit is 0.1354. So the proof as printed delivers δ = 1/8 for α = 1/4 only for n ≥ 11, and the theorem, Step 2 and the remark after Theorem 2 state it without that condition. Observation 2 (α = 1/5, n ≥ 4) checks out: 0.1107 ≥ 0.1. The complexity result is not affected since any positive constant suffices. Square roots were evaluated by hand: √(4/3) = 1.15470, √(10/9) = 1.05409, √(11/10) = 1.04881.
Second check: another model agreed
Report a problem with this finding
Wording Proof of Theorem 4 (p.384) prints f(x)−(f(a0)+f̃(x)) = Σ_j ln c′ᵀx/x_j − Σ_j ln c′ᵀa0/a0j − n Σ ln c′ᵀx/c′ᵀa0; the Σ in the last term is spurious given f̃(x)=n ln c′ᵀx/c′ᵀa0.
- p. 12 Proof of Theorem 4, display between (1) and (2)
− n ∑ ln (c'^T x / c'^T a_0)
- p. 12 Proof of Theorem 4, display before (2)
− n Σ ln c'ᵀx / c'ᵀa0
Only the authors can say what is right here.
Judge's note: The image shows 'n Σ ln' in the last term. With the definition f̃(x)=n ln(c′ᵀx/c′ᵀa0) on the same page, the right-hand side reduces to −Σ_j ln(x_j/a0j), as the next line states, only if the extra Σ is removed. Summing over j would give n² ln(...), and the cancellation fails. The stated result is unaffected.
Second check: another model agreed
Report a problem with this finding
Wording Section 5, Step 4, property 5 (p. 387): "∑_{i=1}^{n+1} c_i a_i x′_i / x′_{n+1} = 0" — the sum should run to n; c and a are in Rⁿ, so c_{n+1} and a_{n+1} are undefined.
- p. 15 Section 5, Step 4, property 5, display after 'we get'
∑_{i=1}^{n+1} c_i a_i x'_i / x'_{n+1} = 0
Judge's note: Viewed page 15. The upper limit printed is n+1. The sum comes from substituting x_i = a_i x′_i / x′_{n+1} (i = 1..n) into cᵀx = 0 with c, x ∈ Rⁿ; the analogous sum for A at the top of the page runs to n. The (n+1)-th component only appears afterwards through c′_{n+1} = 0. Limit typo, result unaffected.
Second check: another model agreed
Report a problem with this finding
Wording Problem P′ (5) uses "xᵀQx ≦ α′r" (radius, not squared radius), so "(Taking Q=I and α′=α corresponds to the original problem.)" and the inclusions "{x|xᵀQx ≦ α′r} ⊆ B(a₀, 2α′r)" and (12) "… ⊆ B(a₀, αr)∩Ω″" do not hold as printed; the bound should be (α′r)².
- p. 17 Section 6.2, equation (5)
xᵀQx ≤ α′r
- p. 17 Immediately after equation (5)
Taking Q=I and α′=α corresponds to the original problem.
- p. 18 Equation (12), right inclusion
{x|xᵀQx ≤ α′r, Bx=0} ⊆ B(a₀,αr)∩Ω″
- p. 17 Section 6.2, Problem P′, eq. (5)
and xᵀQx ≦ α'r
Only the authors can say what is right here.
Judge's note: Checked p17 (eq. 5 and the parenthetical) and p18 (eqs. 11–13); the image shows α′r without a square throughout. With Q=I, xᵀx≤αr is a ball of radius √(αr), not αr. From (11), xᵀQx≥½xᵀx, so the set lies in a ball of radius √(2α′r), not 2α′r. Counterexample, taking u as a displacement: n=3, A=(1,1,−2), α=1/4, α′=1/8, r=1/√6, u=(−0.1,0.1,0). Then Bu=0, uᵀu=0.02≤α′r≈0.0510, but |u|²=0.02>(αr)²=1/96, so u lies outside B(a₀,αr). With the bound written as (α′r)², (11) gives radii α′r/√2 and √2·α′r and both inclusions hold, so the claims in (14)–(15) can be restored. The step is faulty, but the intended result stands after the repair, hence S3.
Second check: another model agreed
Report a problem with this finding
Wording Section 7.3 (p. 394): "prove a worst-case bound of O(n^2.5) arithmetic operations per step", whereas Section 6.3 (p. 391) establishes only that "the average work per step is O(n^2.5)".
- p. 22 Section 7.3, first paragraph
prove a worst-case bound of O(n^2.5)
- p. 19 Section 6.3, first paragraph
the average work per step is O(n^2.5)
Judge's note: Viewed pages 19, 21 and 22. Section 6.3 bounds the total number of rank-one updates over m steps by O(m√n) (eq. (25)), each costing O(n²), and states the result as average work per step. A single step can need up to n updates, so no per-step worst-case bound of O(n^2.5) is proved. The concluding remark drops the averaging qualifier. It can be read as worst case over inputs of the amortised cost, so this is a wording overstatement, not a wrong result.
Second check: another model agreed
Report a problem with this finding
19 minor (typos and the like; most checked by the judge only)
Reference or label Section 6.3 (p. 392): "By equations (20) and (21)," introduces ln√2·n_i ≦ ∑_k |ln Δ_i^(k)|, which needs (21) and (22); (22) is not cited.
- p. 20 Section 6.3, before the unnumbered inequality preceding (23)
By equations (20) and (21),
Judge's note: Viewed page 20. (21) gives ln√2 ≤ ∑|Δδ_i^(k)| between two updates; turning |Δδ_i^(k)| into |ln Δ_i^(k)| is exactly equation (22), printed just above. (20) is only the definition of Δδ and is already used in (21). The pointer is off by one, and the same shift appears at C027. Minor because (22) sits immediately before the sentence.
Second check: another model agreed
Report a problem with this finding
Wording Proof of Theorem 3: 'Let x* be the point in Ω″∩S where the minimum of c′ᵀx is achieved' uses S, which is undefined here (in §1.2 S denotes a sphere); the simplex Δ is meant.
- p. 10 Proof of Theorem 3, first sentence
Let x* be the point in Ω″∩S where the minimum of
- p. 2 Section 1.2
where S is a sphere
- p. 10 Proof of Theorem 3, first sentence
Let x* be the point in Ω''∩S where the minimum of c'ᵀx is achieved.
Judge's note: In the p.382 image the set is Ω″∩S. The argument needs x* to be in the transformed simplex (c′ᵀx*=0, |x*−a0| ≤ R, the circumscribing radius on p.383). The simplex is Δ throughout. Grep finds only one other S, on p.2, defined as 'a sphere'. The proof is correct if S is read as Δ.
Second check: another model agreed
Report a problem with this finding
Wording Step 1.1: "This guarantees that Ker B⊆Σ", but Σ is defined in Section 1.4 as {x | Σ x_i = 1}, while every vector in Ker B has component sum 0.
- p. 6 Section 2.3, Step 1, substep 1
This guarantees that Ker B⊆Σ.
- p. 3 Section 1.4, definition of Σ
Σ = {x | ∑ x_i = 1}
- p. 9 Section 3.4
any displacement in Ω″ is in the null space of B
Only the authors can say what is right here.
Judge's note: Enlarged page 6 crop shows "Ker B ⊆ Σ". Page 3 defines Σ as the hyperplane with component sum 1. B has a row of ones, so Ker B lies in the parallel subspace with sum 0 and is disjoint from Σ as defined. Section 3.4 (page 9) has the correct form: displacements in Ω″ are in the null space of B, Ω″ = u + Ker B. The intended meaning (directions parallel to Σ) is clear, so this is loose notation and not an error in the algorithm.
Second check: another model agreed
Report a problem with this finding
Wording The projection "cₚ = [I−Bᵀ(BBᵀ)⁻¹B]Dc" (Step 1.2; also Algorithm A) needs BBᵀ to be invertible, but the canonical form ("Input: A∈Zᵐˣⁿ, c∈Zⁿ") states no full-row-rank assumption and no removal of dependent rows.
- p. 5 Section 2.1, input and assumptions
A ∈ Zᵐˣⁿ
- p. 6 Step 1, substep 2
cₚ = [I−Bᵀ(BBᵀ)⁻¹B]Dc
- p. 9 Algorithm A, substep 1
cₚ = [I−Bᵀ(BBᵀ)⁻¹B]c′
Only the authors can say what is right here.
Judge's note: Checked p5: the assumptions list only cᵀx≥0, Aa₀=0 and cᵀa₀≠0, with no rank condition. Checked p6 and p9 for the projection formula. Recomputed the example: A has rows (1,−1,0) and (2,−2,0), D=I/3, B=[AD; eᵀ]. Then BBᵀ=[[2/9,4/9,0],[4/9,8/9,0],[0,0,3]], whose leading 2×2 block has determinant 0, so BBᵀ is singular. The instance meets all stated assumptions. This is a missing standard assumption (full row rank, or a pseudo-inverse), not a substantive error, so it is minor.
Second check: another model agreed
Report a problem with this finding
Wording Step 1.4: "b' = a0 − αr ĉ i.e. take a step of length αr in the direction ĉ"; the formula steps in the direction −ĉ, as Algorithm A says ("along the direction −ĉ_P").
- p. 6 Section 2.3, Step 1, substep 4
take a step of length αr in the direction ĉ
- p. 9 Algorithm A, step 3
Take a step of length αr along the direction −ĉ_P
Judge's note: Page 6 image shows the minus sign in the formula and "in the direction ĉ" in the prose. Page 9 Algorithm A step 3 prints "along the direction −ĉ_P" for the same computation. The formula is unambiguous, so only the wording is wrong.
Second check: another model agreed
Report a problem with this finding
Wording Step 1.3 "ĉ = cₚ/|cₚ|" (and Algorithm A step 2 "ĉₚ = cₚ/|cₚ|") has no branch for cₚ=0, which can occur on admissible inputs with a positive optimum; the normalisation is then undefined.
- p. 6 Step 1, substep 3
ĉ = cₚ/|cₚ|
- p. 9 Algorithm A, substep 2
ĉₚ = cₚ/|cₚ|
Only the authors can say what is right here.
Judge's note: Checked p6 and p9: there is no handling of cₚ=0. Verified the example: A=(1,−1,0), c=(1,1,1), D=I/3. B has rows (1/3,−1/3,0) and (1,1,1), and BBᵀ=diag(2/9,3) is invertible. B·Dc=(0,1), (BBᵀ)⁻¹(0,1)=(0,1/3), and Bᵀ(0,1/3)=(1/3,1/3,1/3)=Dc, so cₚ=0 and ĉ=0/0. The infeasibility check in Step 2 (p7) comes after this step. This is related to C004 (an unhandled positive optimum) but is a distinct defect in the algorithm itself. It is an edge case, so minor.
Second check: another model agreed
Report a problem with this finding
Wording Theorem 4 states 'For α=1/4 we may take δ=1/8' (also Step 2 'δ=1/8', after Theorem 2 'δ≧1/8', §3.4 'δ>1/8 in Theorem 2'), but the proof (p.384) only establishes 'If α=1/4, then lim δ(n)≧1/8'; its δ(n) is below 1/8 for n ≤ 10.
- p. 7 Section 2.3, Step 2
δ=1/8
- p. 8 After Theorem 2
then δ≧1/8
- p. 9 Section 3.4
corresponds to δ>1/8
- p. 9 Theorem 4
may take δ=1/8
Only the authors can say what is right here.
Judge's note: Reworked p.384: δ(n)=α−α²/2−α²n/((n−1)[1−α√(n/(n−1))]). For α=1/4: n=4 gives 0.1016, n=10 gives 0.1245, n=11 gives 0.1256, limit 0.1354. So the bound the proof derives reaches 1/8 only for n ≥ 11. Theorem 4 and Step 2 state δ=1/8 without any condition on n. The only finite-n bound in the proof is for α=1/5 (δ≧1/10, n≧4). The sharper intermediate bound from Theorem 3's proof, ln(1+nα/(n−1−α)), would probably close the gap, so the statement–proof mismatch is filed as a query. Separately, the relation is printed as '=' (Step 2, Thm 4), '≧' (after Thm 2) and '>' (§3.4, which attributes it to Theorem 2, where it is printed ≧).
Second check: another model agreed
Report a problem with this finding
Wording Proof of Theorem 4 (p. 384) writes f throughout ("By Theorem 3, f(a₀) − f(b_m) ≧ ln (1+α)") although Theorems 3 and 4 are stated for the transformed potential f′ ("f′(b′) ≦ f′(a₀) − δ").
- p. 12 Proof of Theorem 4, equation (1)
f(a_0) − f(b_m) ≧ ln (1+α).
- p. 9 Theorem 3
f′(b′)≦f′(a_0)−δ
Judge's note: Viewed pages 9 and 12. Theorems 3 and 4 on p. 381 are stated with f′; the proof on p. 384 uses f(a₀), f(b_m), f(b′), f(x) while expanding with c′, i.e. it means f′. The proof of Theorem 2 directly below uses f′ for the transformed and f for the original potential, so the two symbols are distinct in the paper. The prime is dropped consistently in the proof and the argument is unaffected, hence minor.
Second check: another model agreed
Report a problem with this finding
Wording In (12)–(13) the set "{x|xᵀQx ≤ α′r, Bx=0}" (vectors in Ker B, where eᵀx=0) is compared with "B(a₀,αr/4)∩Ω″" (points with eᵀx=1) and f′(x) is minimised over it, with no translation by a₀; as printed, the inclusions fail and f′ is undefined on that set.
- p. 17 Section 6.2, equation (5)
subject to Bx = 0
- p. 18 Equation (12)
B(a₀,αr/4)∩Ω″ ⊆ {x|xᵀQx ≤ α′r, Bx=0}
- p. 18 Equation (13)
min {f′(x)|xᵀQx ≤ α′r, Bx=0}
Only the authors can say what is right here.
Judge's note: Checked p9 (B includes the row eᵀ; 'any displacement in Ω″ is in the null space of B'), p17 (eq. 5, Bx=0) and p18 (eqs. 12–13 and the inclusion after 11). a₀ lies in the left set of (12), but eᵀa₀=1≠0, so a₀ is not in the middle set. The zero vector is in the middle set but |0−a₀|²=1/3>(αr)²=1/96, so the right inclusion fails. Every nonzero x with eᵀx=0 has a nonpositive component, so f′(x) in (13) is undefined there. Reading x as a displacement in (5) is natural, so this is a notational defect, repaired by writing a₀+u in (12)–(13). It is distinct from the missing square in C029.
Second check: another model agreed
Report a problem with this finding
Typo Section 1.3: "Let a0 be strictly interior point in the polytope P." is missing the article "a" before "strictly interior point".
- p. 2 Section 1.3, first sentence
Let a0 be strictly interior point in the polytope P.
Judge's note: Read on the page 2 image; the sentence is printed as quoted. Plain missing word.
Second check: none (judge only)
Report a problem with this finding
Typo Section 1.4: "The transformation C(a, a0) has the following properties" should read T(a, a0); C is the diagonal matrix and is never given arguments.
- p. 3 Section 1.4, sentence before property 1
The transformation C(a, a_0) has the following properties
- p. 3 Section 1.4, sentence after the diagonal matrix C
The transformation C(a, a0) has the following properties
- p. 3 Section 1.4, definition of the transformation
T(a, a0) of the hyperplane
Judge's note: Page 3 image: the transformation is introduced as "T(a, a0)" a few lines above, the matrix as "C = diag(1/a1, ..., 1/an)", and the property list starts "T is one-to-one". Sections 3.2 and 3.3 (page 8) use T(a, a0). Wrong symbol, harmless to the mathematics.
Second check: none (judge only)
Report a problem with this finding
Typo The projected cost vector is written "c_p = [I−B^T(BB^T)^−1B] Dc" with a lower-case subscript in Step 1.2 and "c_P = [I−B^T(BB^T)^−1B]c′" with a capital subscript in Algorithm A.
- p. 6 Step 1.2
cp = [I−B^T(BB^T)^−1B] Dc
- p. 9 Algorithm A
cP = [I−B^T(BB^T)^−1B]c′
Judge's note: Page 6 image and an enlarged page 9 crop show lower-case p in Section 2.3 and a small capital P in Section 3.4. Same quantity (c′ = Dc). Cosmetic notation inconsistency.
Second check: none (judge only)
Report a problem with this finding
Typo Section 3.4, before Algorithm A: "an algorithm to minimize c′^T x, over B(a0, α*r)"; the radius is αr everywhere else, and Theorem 5 states the domain as B(a0, αr)∩Ω″.
- p. 9 Section 3.4, sentence before Algorithm A
over B(a_0, α*r).
- p. 9 Theorem 5
minimizes c'^T x over B(a_0, αr)∩Ω″
- p. 9 Section 3.4, before Algorithm A
B(a0, α*r)
- p. 9 Section 3.4, Theorem 5
B(a0, αr)∩Ω″
Judge's note: Page 9 image shows a raised asterisk between α and r in this sentence only. Theorems 3, 4 and 5 and Algorithm A step 3 on the same page print αr, and no α* is defined anywhere. The sentence also omits the intersection with Ω″ that Theorem 5 gives for the same algorithm.
Second check: none (judge only)
Report a problem with this finding
Typo Proof of Theorem 3, display for f′(a0)−f′(b′): the factor "b_j / a_0j" is printed without a prime; it should be b′_j / a_0j.
- p. 10 Proof of Theorem 3, display after 'Hence'
b_j / a_{0j}
Judge's note: Enlarged page 10 crop: the line above reads "b′_j = (1−λ)a_0j + λx*_j" with a clear prime, and the next display has b_j with none. The right-hand side substitutes the expression for b′_j, so b′_j is meant. Unprimed b is the output point in the original space.
Second check: none (judge only)
Report a problem with this finding
Typo Section 5 Step 1: 'this combined problem is feasible if and only the original problem has finite optimum solution' is missing 'if' (and an article).
- p. 13 Section 5, Step 1, last sentence
is feasible if and only the original problem
- p. 13 Section 5, Step 1, sentence after the system
this combined problem is feasible if and only the original problem has finite optimum solution
- p. 13
this combined problem is feasible if and only the original problem
Judge's note: Confirmed on the p.385 page image; the word is missing in print.
Second check: none (judge only)
Report a problem with this finding
Typo Section 5 numbers two consecutive steps 'Step 3' ('Introduce an artificial variable…' and 'Change of Notation'), followed by 'Step 4'; the later reference 'the problem in Step 3' is thus ambiguous.
- p. 14 Section 5, first Step 3
Step 3. Introduce an artificial variable
- p. 14 Section 5, second Step 3
Step 3. Change of Notation.
- p. 14 Section 5, Step 3 (artificial variable)
Step 3. Introduce an artificial variable to create an interior starting point.
- p. 14 Section 5, next step
Step 4. A projective transformation of the positive orthant into a simplex.
Judge's note: Confirmed on the p.386 image: the sequence is Step 1, 2, 3, 3, 4. The second Step 3 should be Step 4 and the projective transformation Step 5. The text 'if the problem in step 2 is feasible' is consistent.
Second check: none (judge only) · checked by hand
Report a problem with this finding
Typo Section 6.1: 'we exploit the following facts about matrix inserve' — 'inserve' should be 'inverse'.
- p. 16 Section 6.1, paragraph after equation (1)
facts about matrix inserve
- p. 16
we exploit the following facts about matrix inserve:
Judge's note: The crop image of p.16 shows 'inserve' in print.
Second check: none (judge only)
Report a problem with this finding
Typo Section 7.3 (p. 394): "(as described in section 2)" uses lower-case "section" where numbered cross-references elsewhere are capitalised ("Section 6", "Section 5", "Section 6.3").
- p. 22 Section 7.3
(as described in section 2)
Judge's note: Viewed page 22 and searched the text layer for numbered section references: "Section 6", "Section 5" and "Section 6.3" are capitalised; this is the only lower-case numbered one. Purely a capitalisation inconsistency. The reviewer's side remark about "step 2" on p. 7 being the wrong step was not part of this cluster's quotes and was not adjudicated here.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [4] prints the issue designation as a letter: "Doklady Akademii Nauk SSSR 244:S (1979), 1093—1096"; an issue number should be a numeral (probably "244:5").
- p. 23 Reference [4]
244:S (1979), 1093—1096
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: that the Khachiyan paper appeared in issue 5 of Doklady Akademii Nauk SSSR volume 244. Viewed the crop and the full page 23 image. The glyph after "244:" is a capital letter S, visibly different from the numerals in the same entry ("1093—1096", "20:1", "191—194"), so this is not an extraction artefact. The same reference gives the translation as "20:1", a volume:issue pattern with a numeric issue, so a letter is internally inconsistent and a numeral was evidently intended. That the intended numeral is 5 cannot be verified from the files. Cosmetic typo in the reference list; the reference remains locatable by volume, year and pages.
Second check: none (judge only)