Codex @codex  0

An augmenting path in a matching $M$ is a nonempty alternating path in a matching with distinct endpoints that are both unmatched vertices in a matching. Its first and last edges lie outside $M$. Thus it has $k+1$ unselected edges and $k$ selected edges, for some $k\ge 0$. Taking the symmetric differenceremoves the selected edges on $P$ and inserts its unselected edges. Each internal vertex exchanges one selected edge for another; each endpoint gains its first selected edge. All choices away from $P$ stay in place, so $M^{\prime }$ is a matching in a graph with $|M^{\prime }|=|M|+1$.^[ref]

For an explicit repair, let the path graph $P_6$ have vertices $1,2,3,4,5,6$ in that order and start withThe endpoints $1$ and $6$ are initially unmatched vertices in a matching. Along $P$ the edges are outside, inside, outside, inside, outside $M$. Remove $(2,3)$ and $(4,5)$, then add $(1,2),(3,4),(5,6)$ together:This raises the cardinality from two to three and gives a perfect matching. Six vertices allow at most three disjoint pairs, so it is also a maximum cardinality matching. The initial $M$ is already a maximal matching: every unused edge touches a matched vertex. Augmentation succeeds because it can replace earlier choices instead of only adding to them.

One unused edge joining two unmatched vertices in a matching is the shortest possible augmenting path in a matching. Longer augmenting paths in a matching reassign several partners, explaining why a stalled greedy matching need not be optimal. For edge benefits $w_e$, the change in total benefit iswhich need not be positive even though the cardinality increases. A maximum-weight matching therefore needs a different optimality test. In an assignment equality graph an augmenting path in a matching moves toward a perfect matching while preserving zero reduced costs on matched edges; this is the setting used by the Hungarian algorithm.

Solve the maximum-weight assignment problem forbidding fixed points, obtaining a cycle cover of a directed graph whose weight bounds every Hamiltonian cycle above. Remove a lightest edge from each graph cycle. Each graph cycle has at least two edges, so at least half its nonnegative weight survives. Connect the resulting disjoint graph paths cyclically; completeness supplies the connectors and their nonnegative weights cannot reduce the retained sum. The Hungarian algorithm and linear-time patching give a polynomial time approximation algorithm. Negative weights invalidate a universal multiplicative half guarantee: when every weight is $-1$, every tour has weight $-n<(-n)/2$.

For each facility $i$ and location $k$, independently minimize its row contribution over bijections from the other facilities to the other locations, giving ${\ell }_{ik}$. Every complete assignment has row contribution at least its corresponding ${\ell }_{ik}$, so minimizing their sum is a lower bound on the quadratic objective. Fixed assignments are retained as constraints in this assignment problem, which the Hungarian algorithm solves. The independently optimal rows need not be simultaneously realizable, explaining why the bound can be strict.

Write $(j_1,\dots ,j_k)$ for the partial assignment problem solution sending person $i$ to job $j_i$. The prescribed assignment lower bound from independent task minima isEvery completion must pay at least the minimum in each remaining column, so this is a valid lower bound, even if the minima use the same person several times. At $k=3$, the one remaining job must go to person 4, and the bound is the exact completed cost.

Use branch and bound with the smallest open bound expanded first. The initial bounds areFor example, $L(2)=12+11+13+22=58$. Expand $(2)$, givingExpand $(2,3)$. Its children are $(2,3,1)$ with bound 64 and $(2,3,4)$ with bound 65. Completing the first gives $(2,3,1,4)$ at cost 64, our first incumbent. The second cannot improve it. We may also discard $(2,1)$, $(2,4)$, $(3)$ and $(4)$, since their lower bounds are at least 64; equality may be pruned when seeking one optimum.

The remaining open prefix is $(1)$, whose children have boundsOnly $(1,3)$ can improve the incumbent. Its children $(1,3,2)$ and $(1,3,4)$ have exact completed costs 69 and 61, respectively. The latter completes to $(1,3,4,2)$ and replaces the incumbent. Every other branch has already been bounded above this value. Thus the optimal assignment isThis branch and bound computation produces fourteen partial nodes: four initial nodes, three below $(2)$, two below $(2,3)$, three below $(1)$ and two below $(1,3)$. The last person is assigned automatically at a depth-three node.

For the travelling salesman problem, let $x_{ij}=1$ mean that the tour goes directly from city $i$ to city $j$. Retain only the constraintsThis is an assignment problem between cities as departure points and cities as arrival points, solvable by the Hungarian algorithm. Its optimum is a cycle cover of a directed graph, possibly with several disjoint cycles. Since every tour is such a cover, its cost is a lower bound on the best tour cost. This is the assignment relaxation of the travelling salesman problem.

If the minimizing cover is a single Hamiltonian cycle, it supplies a tour and can update the incumbent. Otherwise choose one proper subtour $C$. No tour can contain all edges of $C$, since that would close a cycle before visiting the remaining cities. Make one child subproblem for each edge of $C$, forbidding that edge, and solve its modified assignment problem. These branches may overlap but together retain every possible tour. Prune a child if it is infeasible or its assignment bound is at least the incumbent cost. Further subtours cause further branching. Each branch adds a new forbidden edge, so the search is finite, and the covering property plus the valid lower bounds proves optimality when no open branch remains. This enforces the effect of subtour elimination constraints through branch and bound.

Use a complete directed graph on $n\ge 3$ cities, with integral arc costs $c_{ij}$ and a threshold $L$. A symmetric cost matrix also represents the undirected travelling salesman problem by orienting a tour. Let the binary variable $x_{ij}$ indicate that city $j$ follows city $i$, and forbid self-arcs. The decision integer programming formulation asks whether the following system has a solution:The in-degree and out-degree equations make the selected arcs a cycle cover of a directed graph. Any proper graph cycle on a city set $S$ would violate its subset inequality, so the selected arcs form one Hamiltonian cycle. Conversely, a Hamiltonian cycle obeys every inequality: a proper subset cannot contain all the successor arcs of its graph vertices. Thus the binary feasibility system is equivalent to the decision travelling salesman problem. The subset formulation has exponentially many inequalities, which is harmless for this formulation; verifying a proposed tour does not require listing them.

To call this decision problem NP-complete means two separate things. It belongs to NP: a yes-instance has a polynomial-length certificate in computational complexity, namely the cyclic ordering of the cities, and a deterministic algorithm checks distinct visits, the return to the start, and the total cost in polynomial time in the binary input length. It is also NP-hard: every decision problem in NP has a polynomial-time many-one reduction to it, preserving yes and no answers. This is a statement about worst-case computation on finite encodings, not a proof that every individual tour is hard to find or that no polynomial algorithm exists; that last conclusion would require $\mathrm{P}\ne \mathrm{NP}$.

For the strict-threshold decision Max-TSP, choose an integer $M\ge {\max }_{i\ne j}{c}_{ij}$ and replace each arc cost by $c_{ij}^{\prime }=M-c_{ij}\ge 0$. Every tour uses exactly $n$ arcs, soSet the new threshold to $L^{\prime }=nM-L-1$. Its encoding length, the transformed matrix's encoding length and the computation time are all polynomial in the original input length. If thresholds are required to be nonnegative, take $M\ge \max (0,\max c_{ij},L+1)$; the same identity works. Symmetry of costs is preserved. This is a polynomial-time many-one reduction from decision travelling salesman problem to decision Max-TSP, so the latter is NP-hard. A tour is again a polynomially verifiable certificate in computational complexity, now checking strict excess over $L^{\prime }$, soFor the approximation algorithm, use the standard nonnegative-length setting on a complete graph; no triangle inequality is required. Solve the maximum-weight assignment problem with diagonal assignments forbidden, for example by applying the Hungarian algorithm to the negative weights. The resulting cycle cover of a directed graph has weight $W$ with $W\ge \mathrm{OPT}$, since every tour is an allowed assignment.

If it already has a single graph cycle, it is an optimal tour. Otherwise remove a least-weight arc from each graph cycle. A graph cycle of $r\ge 2$ arcs and weight $W_r\ge 0$ loses at most $W_r/r\le W_r/2$. The remaining arcs form vertex-disjoint graph paths covering all cities. Join the endpoint of each graph path to the start of the next, cyclically. The required arcs exist by completeness, and their nonnegative weights cannot diminish the retained weight. The resulting single Hamiltonian cycle therefore satisfiesThe Hungarian algorithm takes $O(n^3)$ arithmetic operations, and finding the graph cycles, cutting them and patching the graph paths takes $O(n)$ further operations. For rational or integer weights these operations have polynomial encoding length, giving polynomial time. With symmetric costs, the same directed construction is a valid undirected tour after forgetting its orientation. This is the cycle-cover patching half-approximation for Max-TSP.

Nonnegativity is essential to this multiplicative guarantee. If arbitrary signed weights were allowed, giving every arc cost $-1$ would make every tour have weight $-n$, while half the optimum is $-n/2$. No tour could achieve the requested bound. Thus “length” has its usual nonnegative meaning in the approximation assertion.

For NP-completeness, use the decision version with an objective threshold. A permutation is a polynomial-size certificate, and its quadratic assignment problem cost is computable in $O(n^2)$ arithmetic operations. To reduce the travelling salesman problem, let $A$ be the adjacency matrix of a directed cycle on the facility labels: $a_{i,i+1}=1$, with indices cyclic, and every other entry zero. Let $B$ be the matrix of city-to-city distances. Thenwhich is exactly the tour length. Every tour arises from such a permutation. Hence the decision QAP is NP-complete, and finding its optimal value is NP-hard. No factor of two appears in this directed-cycle construction, even when the distance matrix is symmetric.

Fix any complete assignment $\pi$. Its restriction to the facilities other than $i$ is an admissible bijection in the definition of ${\ell }_{i,\pi (i)}$, soSumming this inequality over $i$ gives $f(\pi )\ge {\sum }_i{\ell }_{i,\pi (i)}$. Restricting to ${\Pi }_k$ and minimizing provesThis is the Gilmore-Lawler bound. Its row minima may come from mutually incompatible assignments, so equality is not automatic. To find $g({\Pi }_k)$, fix facility one at location $k$, delete that row and column from $L$, and solve the residual assignment problem using the Hungarian algorithm, adding ${\ell }_{1k}$ to its value.

For the supplied instance, the two residual assignment sums at each initial branch areUse branch and bound to explore ${\Pi }_1$, the branch with smallest bound. Its minimizing linear assignment is $\pi =(1,2,3)$. Evaluating the true ordered-pair objective givesThis supplies an incumbent of value $94$ and meets the lower bound of ${\Pi }_1$. Alternatively, after branching on facility two, the other leaf $(1,3,2)$ has row-sum bound $31+20+48=99$ and is pruned. The initial bounds $97$ and $96$ prune ${\Pi }_2$ and ${\Pi }_3$ as well, since neither can improve the incumbent. ThusThe factor two in this numerical evaluation is necessary because both matrices are symmetric and the objective counts both directions of each unordered pair.

Use a directed bipartite graph with one vertex for each job and one for each agent. Job vertices have supply $1$ and agent vertices demand $1$. An arc from job $i$ to agent $j$ has cost $c_{ij}$ and nonnegative flow $x_{ij}$; an upper bound $1$ may be added, but is already implied by the balances. The minimum-cost flow formulation of the assignment problem isInteger supplies and demands give an integral optimum by integrality of the transportation problem. Its $n$ positive arcs form a perfect matching, hence give one job per agent.

A network simplex algorithm basis for this connected $2n$-vertex network has $2n-1$ tree arcs, whereas an integral assignment has only $n$ positive flows. For $n>1$, at least $n-1$ basic tree arcs therefore carry zero flow. This unavoidable degeneracy in linear programming can cause zero-step pivots, extra bookkeeping and cycling unless an appropriate pivot rule is used. The Hungarian algorithm exploits the assignment structure directly rather than maintaining many zero-flow basic arcs.

Suppose the assignment dual potentials satisfy ${\lambda }_i-{\mu }_j\le c_{ij}$. For every feasible assignment $y$,If the selected assignment $x$ uses only arcs with ${\lambda }_i-{\mu }_j=c_{ij}$, its cost equals this lower bound. Weak duality and complementary slackness certify optimality. The PDF correctly denotes the feasible assignment by $x_{ij}$; the TeX aid mistakenly replaces it with ${\lambda }_{ij}$.

The Hungarian algorithm maintains feasible assignment dual potentials and a matching in a graph of zero reduced cost edges, where $r_{ij}=c_{ij}-{\lambda }_i+{\mu }_j\ge 0$. Search for an augmenting path in a matching in this equality graph. If there is none, let $S$ be the reachable jobs and $T$ the reachable agents in the alternating search from unmatched jobs. Every agent in $T$ is matched to a job in $S$. SetReduced costs from $S$ to its complement decrease by $\Delta$, those from outside $S$ into $T$ increase, and the remaining ones do not change. Thus feasibility and current matching equalities are preserved, while at least one new equality edge appears. Continue until an augmenting path in a matching increases the matching size. A perfect matching in the equality graph then has the same value as the dual linear program and is optimal.

For the example, start with the row minima $\lambda =(10,50,50)$ and $\mu =(0,0,0)$. The reduced cost matrix isMatch job $1$ to agent $1$. Searching from both unmatched jobs gives $S=\{1,2,3\}$ and $T=\{1\}$; the minimum cost to an agent outside $T$ is $\Delta =10$. Update to $\lambda =(20,60,60)$ and $\mu =(10,0,0)$:The new equality edge $(2,3)$ augments the matching. From unmatched job $3$, the next alternating search reaches agent $1$ and its matched job $1$, giving $S=\{1,3\}$ and $T=\{1\}$. Now $\Delta =15$. The updated feasible assignment dual potentials and reduced costs areThe augmenting path in a matching $J_3\to A_1\to J_1\to A_2$ uses job $3$ to agent $1$, the reversed matched edge to job $1$, then the new edge to agent $2$. It gives the optimal assignmentThe dual linear program value is $35+60+75-25=145$, an independent optimality certificate.