CMP.6:5 - Archetypal Grounding

CMP.6:5.1 - Construct a discrete local-improvement algorithm

Partition the vertices of an undirected graph into two groups to maximize the total nonnegative weight of edges crossing between groups. Start with any partition. At a vertex v, let I(v) be the weight of its edges to vertices in the same group and C(v) the weight to vertices in the other group. Flipping v changes the cut value by I(v)-C(v).

Compute these differences and flip a vertex whenever its difference is positive. Each flip is an admissible partition change and strictly increases the criterion. Because there are finitely many partitions, the algorithm eventually reaches one with I(v)≤C(v) at every vertex.

At this stopping state, C(v) is at least half the incident weight at v. Summing over vertices counts every cut edge twice, so the cut value is at least half the total graph weight. The total graph weight bounds any cut, giving a factor-two bound relative to the maximum cut. This is a property derived from the chosen neighborhood and nonnegative weights, rather than an assertion that every local optimum is globally optimal.

For a four-cycle with unit weights, start with all vertices in one group. Flipping vertex 1 produces a cut of value 2. Flipping the opposite vertex 3 produces value 4, which is optimal because all four edges cross. Only incident edges need updating after each flip. Finite termination alone does not make the general algorithm polynomial in the encoded input size; the number and cost of flips require a further account.

Changed condition: allow negative edge weights. Take four vertices with weights -3 on edges 1-2 and 3-4, and weight 1 on the four edges between those pairs. With all vertices in one group, each single flip changes the cut by -1, so the algorithm stops at value 0. Moving the pair {1,2} together to the other group produces value 4. Finite termination survives, but the former factor-two guarantee fails. A two-vertex neighborhood opens an improving move; its cost and eventual quality need their own comparison.

CMP.6:5.2 - Derive a step and change its constrained stopping condition

Minimize J(x)=(x-3)² over real x. Its derivative is 2(x-3). The update x'=x-2η(x-3) multiplies the error x-3 by 1-2η. Thus 0<η<1 contracts its magnitude; with η=1, the error oscillates without decreasing.

Choose η=1/4. From x=0, the iterates are 1.5, 2.25, 2.625, ...; the objective values are 9/4, 9/16, 9/64, .... After k steps from the initial point, the distance to 3 is 3/2^k. A requested distance at most epsilon therefore has a directly computable iteration bound. This example establishes the update through its algebra rather than through a generic instruction to repeat until the values seem stable.

Changed constraint: require 0≤x≤1. Projection of the same proposed first step onto this interval gives x=1. Further projected steps remain at 1. The derivative there is -4, so a full-gradient-zero stopping test would never recognize the constrained optimum. Every feasible point in the interval has J(x)≥4=J(1), establishing the result. The changed feasible set requires a changed stopping argument, even though a related update can still be used.