ISyE/Math/CS 425: Introduction to Combinatorial Optimization - Reductions

Vocabulary flashcards covering the formal definitions, algorithm construction, runtime breakdown, proof techniques, and examples of reductions in Combinatorial Optimization.

Reduction of Problem $P_1$ to Problem $P_2$

The process of solving problem $P_1$ by using any algorithm that solves problem $P_2$. Formally, it requires: (i) constructing an instance $I_2$ of $P_2$ from any instance $I_1$ of $P_1$, and (ii) constructing an optimal solution $S_1$ of $I_1$ from an optimal solution $S_2$ of $I_2$.

Algorithm $A_1$ (via Reduction)

An algorithm that solves problem $P_1$ using an algorithm $A_2$ that solves $P_2$ in three steps: (1) construct instance $I_2$ from instance $I_1$, (2) execute $A_2$ on $I_2$ to find optimum solution $S_2$, and (3) use $S_2$ to construct an optimum solution $S_1$ of $I_1$.

Running Time of a Reduction Algorithm

The total running time of algorithm $A_1$, calculated as the sum of: (1) the time required to construct instance $I_2$, (2) the running time of algorithm $A_2$ on instance $I_2$, and (3) the time required to construct solution $S_1$.

Connector Problem

A combinatorial optimization problem defined on a connected graph $G = (V, E)$ with positive edge costs $c_e$ for every $e \times E$, where the goal is to find an optimum spanning connected subgraph $H_1 = (V, T)$.

Reduction of Connector Problem to MST

A reduction where instance $I_2$ of the Minimum Spanning Tree (MST) problem coincides with instance $I_1$ ($G = (V, E)$ with positive costs $c_e$), and the optimum spanning connected subgraph $H_1 = (V, T)$ of $I_1$ directly coincides with the MST $H_2$ of $I_2$.

Lemma 2.1

A lemma stating that if edges in circuits of a spanning connected subgraph are recursively removed until no circuits remain, the resulting subgraph is acyclic, spanning, and connected (a spanning tree) with cost at most that of the original subgraph.

Minimization Reduction Conditions (Same Objective Function)

Sufficient conditions to prove solution correctness when both problems minimize cost function $c$: (a) given any solution $S_2$ of $I_2$, construct $S_1$ of $I_1$ with $c(S_1) \le c(S_2)$; (b) given any solution $\bar{S}_1$ of $I_1$, construct $\bar{S}_2$ of $I_2$ with $c(\bar{S}_2) \le c(\bar{S}_1)$.

Maximization Reduction Conditions (Same Objective Function)

Sufficient conditions to prove solution correctness when both problems maximize objective function $c$: (a) given any solution $S_2$ of $I_2$, construct $S_1$ of $I_1$ with $c(S_1) \ge c(S_2)$; (b) given any solution $\bar{S}_1$ of $I_1$, construct $\bar{S}_2$ of $I_2$ with $c(\bar{S}_2) \ge c(\bar{S}_1)$.

Proof of Reduction Correctness via Contradiction

The standard general method to prove $S_1$ is optimal by assuming a strictly better solution $\bar{S}_1$ exists for $I_1$, using it to construct a solution $\bar{S}_2$ for $I_2$ that is strictly better than $S_2$, thereby contradicting the optimality of $S_2$.

Euclidean Matching

The target optimization problem to which the Plotter problem is reduced.