Combinatorial Optimization - Problems and Algorithms

Flashcards covering key terms, theorems, and algorithm complexity for the Euclidean Traveling Salesman Problem, Circuit Drawing Problem, and Euclidean Matching Problem from ISyE/Math/CS 425.

Euclidean Traveling Salesman Problem (TSP)

A combinatorial optimization problem where given a set $V = \{(x_i, y_i) : i = 1, \dots, n\}$ of points in the Euclidean plane, the objective is to find a tour passing through each point of $V$ once, for which the sum of the distances $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$ is minimized.

Brute Force Algorithm for TSP

An exact algorithm for TSP that lists all $\frac{(n - 1)!}{2}$ different possible tour solutions, evaluates each one, and picks the best solution.

Nearest Neighbor Algorithm

A fast heuristic algorithm for TSP that picks an arbitrary starting point, repeatedly moves to the nearest unvisited point, and returns to the starting point upon visiting all points, though it does not guarantee an optimal solution.

Pen-Up Time

In the circuit drawing problem, the time during which the plotter pen is moved without contacting the paper surface.

Pen-Down Time

In the circuit drawing problem, the fixed time during which the plotter pen actually draws lines on the paper.

Node (Circuit Drawing)

A point in a figure from which a positive number of lines emanates, excluding points with degree $2$.

Odd Node

A node in a figure that has an odd number of lines emanating from it.

Even Node

A node in a figure that has an even number of lines emanating from it.

Euclidean Matching Problem

A combinatorial optimization problem where given a set $V$ of points in the Euclidean plane with $|V|$ even, the objective is to find a set of lines such that each point is an end of exactly one line and the sum of line lengths is minimized.

Problem Size

In combinatorial optimization, the length of an encoding of the discrete structure plus the cardinality of the set of numbers used, such as $s = 2n$ for an $n$-point Euclidean TSP instance.

Polynomial-Time Algorithm

An efficient algorithm whose running-time bound is $O(s^k)$ for some $k \in \mathbb{N}$, where $s$ is the problem size, ensuring running time does not grow excessively fast as size increases.

Big-O Notation

An asymptotic bounding notation where $f(s) \in O(g(s))$ if there exists a constant $c > 0$ such that $f(s) \le c \cdot g(s)$ for all sufficiently large values of $s$.

Nearest Neighbor Time Complexity

The upper bound on elementary operations for the Nearest Neighbor algorithm, calculated as at most $3n + (n - 1)((n - 1) \times 9 + 2)$ steps, which is $O(n^2)$ or $O(s^2)$ where instance size $s = 2n$.

Euclidean Traveling Salesman Problem (TSP)

A combinatorial optimization problem where given a set $V = \{(x_i, y_i) : i = 1, \dots, n\}$ of points in the Euclidean plane, the objective is to find a tour passing through each point of $V$ once, for which the sum of the distances $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$ is minimized.

Brute Force Algorithm for TSP

An exact algorithm for TSP that lists all $\frac{(n - 1)!}{2}$ different possible tour solutions, evaluates each one, and picks the best solution.

Nearest Neighbor Algorithm

A fast heuristic algorithm for TSP that picks an arbitrary starting point, repeatedly moves to the nearest unvisited point, and returns to the starting point upon visiting all points, though it does not guarantee an optimal solution.

Pen-Up Time

In the circuit drawing problem, the time during which the plotter pen is moved without contacting the paper surface.

Pen-Down Time

In the circuit drawing problem, the fixed time during which the plotter pen actually draws lines on the paper.

Node (Circuit Drawing)

A point in a figure from which a positive number of lines emanates, excluding points with degree $2$.

Odd Node

A node in a figure that has an odd number of lines emanating from it.

Even Node

A node in a figure that has an even number of lines emanating from it.

Circuit Drawing Traversability Theorem

A theorem stating that a figure can be drawn, returning to the starting point, without tracing the same line twice and with no pen-up motion if and only if it is connected and there are no odd nodes.

Even Number of Odd Nodes Theorem

A theorem stating that in any graph or figure, there is always an even number of odd nodes.

Euclidean Matching Problem

A combinatorial optimization problem where given a set $V$ of points in the Euclidean plane with $\|V\|$ even, the objective is to find a set of lines such that each point is an end of exactly one line and the sum of line lengths is minimized.

Problem Size

In combinatorial optimization, the length of an encoding of the discrete structure plus the cardinality of the set of numbers used, such as $s = 2n$ for an $n$-point Euclidean TSP instance.

Polynomial-Time Algorithm

An efficient algorithm whose running-time bound is $O(s^k)$ for some $k \in \mathbb{N}$, where $s$ is the problem size, ensuring running time does not grow excessively fast as size increases.

Big-O Notation

An asymptotic bounding notation where $f(s) \in O(g(s))$ if there exists a constant $c > 0$ such that $f(s) \le c \cdot g(s)$ for all sufficiently large values of $s$.

Nearest Neighbor Time Complexity

The upper bound on elementary operations for the Nearest Neighbor algorithm, calculated as at most $3n + (n - 1)((n - 1) \times 9 + 2)$ steps, which is $O(n^2)$ or $O(s^2)$ where instance size $s = 2n$.

Spanning Subgraph

A subgraph $H$ of a graph $G = (V, E)$ that includes all vertices of $G$, satisfying $V(H) = V(G)$.

Circuit (Graph Theory)

An edge-simple, closed path $P = v_0, e_1, v_1, \dots, e_k, v_k$ in a graph where $k \ge 1$ and the vertices $v_0, \dots, v_{k-1}$ are distinct.

Forest

A graph that contains no circuits.

Tree

A connected forest, defined as a connected graph containing no circuits.

Minimum Spanning Tree (MST) Problem

The problem of finding a spanning tree in a connected weighted graph $G$ that minimizes the total sum of edge costs.

Kruskal's Algorithm

A minimum spanning tree algorithm that maintains a spanning forest $H = (V, F)$ and iteratively adds the lowest-cost edge that does not create a circuit until $H$ becomes connected.

Prim's Algorithm

A minimum spanning tree algorithm that maintains a tree $H$ starting from an arbitrary root vertex $r$ and iteratively adds the lowest-cost edge connecting a vertex inside $H$ to a vertex outside $H$.

Cut (Graph Theory)

For a graph $G = (V, E)$ and a subset of vertices $U \subseteq V$, the set of edges $\delta(U) = \{e \in E : e = uv, u \in U, v \in V \setminus U\}$ crossing between $U$ and $V \setminus U$.

Trivial Cut

A cut $\delta(U)$ formed when $U = \emptyset$ or $U = V$, containing no edges.

Spanning Tree Edge Count Theorem (Lemma 2.2)

A theorem stating that a connected, spanning subgraph of a graph with $n$ vertices is a spanning tree if and only if it contains exactly $n - 1$ edges.

Cut Property for Minimum Spanning Trees (Theorem 2.4)

A theorem stating that if a subset of edges $B$ is extendible to an MST and $e$ is a minimum-cost edge in a cut $D$ with $D \cap B = \emptyset$, then $B \cup \{e\}$ is also extendible to an MST.

Prim's Algorithm Time Complexity

The asymptotic running time bound of Prim's algorithm when scanning edge lists for cut edges across $n - 1$ iterations, given by $O(nm)$ for a graph with $n$ vertices and $m$ edges.

Kruskal's Algorithm Time Complexity

The asymptotic running time bound of Kruskal's algorithm, combining edge sorting in $O(m \log(m))$ and component merges/finds in $O(m + n^2)$, yielding $O(m \log(m) + n^2)$.