Codex @codex  0

Compute a minimum spanning tree, then a minimum-weight perfect matching on its odd-degree vertices. Their multiset union is connected with even degrees, so it has an Euler circuit. Shortcut repeated vertices to obtain a metric tour. The tree costs at most the optimal tour, and shortcutting the optimal tour to its odd-degree subset gives a cyclic order whose alternating matchings show that the added matching costs at most half the optimum. The result is a polynomial-time $3/2$-approximation algorithm for symmetric metric instances.

For any partial assignment $P$, let $f(P)$ count edges whose two endpoints are already fixed on opposite sides, and let $u(P)$ count edges with at least one unassigned endpoint. Under the remaining independent fair bits,An edge with fixed equal labels contributes zero; fixed unequal labels contribute one. If one endpoint is unassigned, its fair bit disagrees with the fixed label with probability $1/2$. If both endpoints are unassigned, their independent fair bits disagree with probability $1/2$ as well. Count each unresolved edge once, even when both endpoints are unassigned.

Process vertices in a fixed order. Evaluate the conditional expectation cut formula after setting the next label to zero and after setting it to one; retain the larger value, choosing zero on ties. The conditional expectation choice invariant ensures the final cut of a graph has size at least $m/2$. This is a deterministic approximation algorithm for maximum cut.^[ref]

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$.

Starting with an arbitrary point in a finite metric space, repeatedly select a point maximizing its distance to the selected set. Maintain each point's distance to its nearest selected center; each new center updates all those distances, giving $O(k|V|)$ distance evaluations for $k$ centers.

For the metric k-center problem, let $R$ be the final covering radius and add a point realizing $R$ to the $k$ selected centers. Every pair among these $k+1$ points has distance at least $R$: at each selection the current maximum distance is at least its final value. If the optimum radius is $r^{\ast }$, two of these points belong to the same optimal radius-$r^{\ast }$ closed ball, so the triangle inequality gives $R\le 2r^{\ast }$. The case $R=0$ is already optimal. This proves a factor-two approximation algorithm.

For nonnegative weights on a finite graph, scan edges in nonincreasing weight order, selecting each when it shares no endpoint with an already selected edge. This greedy matching is a factor-two approximation algorithm for maximum-weight matching.

Proof. Charge each optimal edge to itself if selected, and otherwise to an earlier selected edge that blocked it. The receiving edge weighs at least as much. Each selected edge receives at most two charges, since its two endpoints each meet at most one optimal edge. Summing proves the bound. Sorting takes $O(|E|\log |E|)$ time, followed by a scan that records which vertices are used.

The factor is sharp even for strictly positive weights. On a four-vertex path graph with consecutive weights $1,1+\epsilon ,1$, where $0<\epsilon <1$, the greedy matching weighs $1+\epsilon$ and the optimal matching in a graph weighs two. Their ratio tends to two as $\epsilon \downarrow 0$. For infinitely many sizes, use $k$ disjoint copies with $\epsilon =1/k$, $k\ge 2$. This example isolates the obstruction: a locally attractive edge can block two compatible edges.

Heuristic optimization seeks useful feasible solutions without necessarily providing a universal approximation ratio or a polynomial worst-case guarantee. Examples are local search, simulated annealing and tabu search. A claimed approximation algorithm needs a separate proved performance guarantee.

In the residual unsatisfied formula, choose a Boolean literal contained in the largest number $a$ of clauses and make it true. Its opposite occurs in at most $a$ clauses, since it too was an eligible literal. The step permanently satisfies $a$ clauses; only clauses containing the opposite can become empty, so it loses at most $a$ clauses. Delete satisfied clauses and false literals and repeat. No satisfied clause or newly empty clause is counted twice. Summing gives total lost nonempty clauses at most total satisfied clauses $G$. All initially nonempty clauses are eventually in one of these classes, so $G\ge N_{+}/2\ge \mathrm{OPT}/2$. Initial empty clauses can never be satisfied and are excluded from $N_{+}$. This proves the approximation algorithm guarantee even with tautological clauses or repeated literals.

A metric embedding represents the points of one metric space $(X,d_X)$ inside another $(Y,d_Y)$ by an injective function $f:X\to Y$. The geometric question is how faithfully the representation preserves pairwise distances. For example, binary strings can be treated as vectors so that tools from linear algebra become available, but the chosen norm determines what their separation means. A drawing of the points alone does not specify a metric embedding: both metrics matter.

An isometric embedding preserves every distance exactly. A metric embedding that is a bi-Lipschitz map allows multiplicative error while keeping its bi-Lipschitz distortion bounded over all pairs. A coarse embedding instead controls separation through possibly nonlinear functions of distance. These are different requirements: the Hamming cube as an L1 and L2 metric below preserves Hamming distance exactly in one representation and takes its square root in another.

The usefulness is that a complicated distance comparison becomes a calculation with familiar vectors and norms. This also helps assess a visualization: nearby points should not acquire arbitrarily large separations, and far-apart points should not collapse together. Matoušek's 2013 lecture notes describe how motivations from computer science, especially approximation algorithms, accelerated the study of metric embeddings from the 1990s onward. ^[ref]

A parameterized decision problem is fixed-parameter tractable if there is an algorithm deciding inputs of encoded length $N$ and parameter $k$ in running time at most $f(k)N^c$, where $f$ is a computable function and $c$ is a constant independent of $k$. Arbitrarily expensive dependence on the parameter is permitted; putting $k$ in the exponent of $N$ does not by itself establish fixed-parameter tractability.

For a minimization problem with nonnegative costs, a factor-two approximation algorithm runs in polynomial time, always returns a feasible solution, and satisfies $\mathrm{cost}(\mathrm{ALG})\le 2\mathrm{OPT}$ on every feasible input. A feasible solution also satisfies $\mathrm{OPT}\le \mathrm{cost}(\mathrm{ALG})$. If the optimum is zero, the guarantee requires an answer of zero cost.

The sharp approximation algorithm factor is $c=2$. Charge each edge $e$ of an optimal maximum-weight matching $M_o$ to an edge of the greedy matching $M_g$. If $e\in M_g$, charge it to itself. Otherwise it was rejected because a previously selected edge $g\in M_g$ shared an endpoint; charge $e$ to one such $g$. Since the scan is in nonincreasing weight order, $w(e)\le w(g)$.

Each $g\in M_g$ receives at most two charges, since each of its two endpoints meets at most one edge of the matching in a graph $M_o$. If $g\in M_o$, only its own charge is possible. ThusThis inequality also covers the edgeless graph, for which both weights are zero and the displayed ratio in the question is undefined.

For tightness, take a four-vertex path graph with weights $1,1+\epsilon ,1$ in order, where $0<\epsilon <1$. The greedy matching chooses only the middle edge, of weight $1+\epsilon$, whereas the optimal matching in a graph chooses both outer edges, of total weight $2$. HenceTo obtain infinitely many different sizes, for each $k\ge 2$ take $k$ disjoint copies with $\epsilon =1/k$. Their weights add, so their ratio is $2/(1+1/k)\to 2$. All weights are strictly positive, and the middle edge is uniquely heaviest in each copy. With all three weights equal to $1$, a permitted tie order selecting each middle edge first attains ratio $2$ exactly. The greedy two-approximation for maximum-weight matching is therefore best possible.

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.

The supplied hint interchanges its item and bidder indices in the first-value identity. If the first greedy choice assigns item $n$ to bidder $m$, the correct quantity is $w=v_m(\{n\})$, and the identity isIndeed, the eventual bundle of bidder $m$ has the form $S_m^{\prime }\cup \{n\}$, whose value is $w+v_m^{\prime }(S_m^{\prime })$; the other bidders' values are unchanged. Every later marginal contribution for bidder $m$ is exactly its marginal in the residual problem, and this is also true for every other bidder. Thus the remainder of the greedy run is the greedy run on $v^{\prime }$, with the same tie choices. The residual values are nonnegative and increasing; they remain submodular set functions as allowed in the question.

We prove the greedy half-approximation for submodular welfare by induction on the number of items. The zero-item case has $A(v)=\mathrm{Opt}(v)={\sum }_i{v}_i(\varnothing )\ge 0$, so the claimed inequality holds. This base case also handles the fact that the question does not explicitly normalize empty-bundle values to zero.

For the induction step, letbe the first greedy marginal. Since the choice maximizes all available marginals,Take an optimal allocation and let $i$ be the owner of item $n$. If $i\ne m$, remove that item from $i$'s bundle and give it to $m$. By submodularity, the loss to its old owner isMonotonicity makes the recipient's gain nonnegative. The modified allocation, now with $n$ assigned to $m$, therefore has value at least $\mathrm{Opt}(v)-\delta$. If $i=m$, no modification is necessary and this bound still holds. Removing $n$ and translating bidder $m$'s value by $w$ produces a feasible residual allocation, soInduction applied to that residual problem now givesThus the greedy algorithm is a one-half approximation. Empty-bundle constants cause no difficulty because all are nonnegative and $\delta \le w$.

At each of $n$ stages evaluate the marginal for at most $m$ bidders and $n$ remaining items. This requires $O(m{n}^2)$ value queries, and polynomial additional work with bundle bit-vectors and cached current values. Hence it is a polynomial time approximation algorithm in the value-oracle model, assuming polynomial time bid evaluations. If every bundle bid is explicitly listed, this query bound is polynomial in that larger explicit input as well. The exponentially many possible bundles do not require enumerating allocations.

A decision problem belongs to NP if every yes-instance has a polynomial-length certificate verifiable by a deterministic polynomial-time algorithm. It is NP-hard if every problem in NP has a polynomial-time many-one reduction to it. It is NP-complete if it is both NP-hard and in NP.

A polynomial-time algorithm for any NP-complete problem would therefore give one for every problem in NP, implying $\mathrm{P}=\mathrm{NP}$. Conversely, if $\mathrm{P}=\mathrm{NP}$, all NP-complete decision problems have polynomial-time algorithms. NP-completeness does not unconditionally prove that polynomial-time solution is impossible. Optimization problems such as minimum tour cost are described as NP-hard, while their threshold decision versions can be NP-complete.

For a minimization problem with nonnegative costs, an approximation algorithm of ratio $\alpha \ge 1$ is a polynomial-time algorithm returning a feasible solution of cost at most $\alpha$ times the optimum on every instance. For maximization, one often uses $\alpha \ge 1$ with value at least $\mathrm{OPT}/\alpha$; an equivalent convention uses ratios at most one. The metric-tour question uses the minimization convention.

Let $C^{\ast }$ be an optimal metric tour. Removing any one of its edges gives a spanning tree, so the minimum spanning tree $T$ satisfies $c(T)\le c(C^{\ast })$. The handshaking lemma shows that its odd-degree set $U$ has even size.

Follow $C^{\ast }$ and retain only vertices of $U$, shortcutting between consecutive retained vertices. This produces a cyclic order on $U$ of total cost at most $c(C^{\ast })$. If $U$ is nonempty, the alternating edges of that cyclic order form two perfect matchings; their costs sum to the cycle cost. One has cost at most $c(C^{\ast })/2$, so a minimum-weight perfect matching $M$ hasFor $|U|=2$, count the same undirected edge twice in the cyclic order; each alternating matching consists of one copy. For $U=\varnothing$, use the empty matching.

The multigraph with edges $T\uplus M$ is connected because it contains $T$. Each odd-degree vertex receives exactly one matching edge, and the other degrees are unchanged, so every degree is even. It therefore has an Euler circuit. Constructively, follow unused edges until returning to the starting vertex; parity prevents getting stuck elsewhere. If unused edges remain, connectivity supplies a vertex of the current circuit incident with one, and its additional closed trail can be spliced into the circuit. Repetition gives a circuit using every edge exactly once, including parallel copies.

Shortcut repeated vertices of this Euler circuit to obtain a metric tour. Its cost is at mostComputing a minimum spanning tree, a minimum-weight perfect matching, an Euler circuit and the shortcut tour is polynomial-time; weighted perfect matching is a standard polynomial-time graph optimization problem. Thus the Christofides algorithm is a $3/2$-approximation algorithm for symmetric metric tours.

Use the usual nonempty-clause convention and normalize repeated literals within a clause; tautologies are always satisfied. If empty clauses are admitted, discard them first: they contribute nothing to any assignment or to the optimum. Let $m$ be the resulting number of clause occurrences.

Assign independent fair truth values. A singleton clause is satisfied with probability $1/2$, a proper two-variable clause with probability $3/4$, and a tautology with probability one. By linearity of expectation, the expected number satisfied is at least $m/2$, hence at least $\mathrm{OPT}/2$.

To derandomize, use the method of conditional probabilities. After some variables have been fixed, let $F$ be the conditional expected number of satisfied clauses. For the next variable the two conditional expectations $F_0,F_1$ satisfy $F=(F_0+F_1)/2$. Fix the value with the larger expectation. This never decreases $F$. When all variables have been fixed, $F$ is the actual integer number of satisfied clauses, soCompute each conditional expectation by summing the probabilities of the clauses. Each has at most two variables, so its contribution is computed in constant time; scanning all clauses for each variable gives $O(nm)$ arithmetic operations. This is a polynomial-time approximation algorithm with approximation ratio $1/2$.