Title: Courses / CS 530

Q: Definition of Approximation Algorithm
A: An \(\alpha\)-approximation for an optimization problem is a polynomial time algorithm which produces a solution of cost within a factor of \(\alpha\) of the optimal solution for every instance.
A randomized \(\alpha\)-approximation instead produces a solution of expected cost within a factor of \(\alpha\) for every input.

Q: PTAS, FPTAS, and APX
A: A polynomial time approximation scheme (PTAS) is a (\(1+\epsilon)\)-approximation for a problem that runs in polynomial time for every fixed \(\epsilon>0\). For example, a PTAS could run in time \(n^{1/\epsilon}\).
A fully polynomial time approximation schme (FPTAS) is a \((1+\epsilon)\)-approximation for a problem that runs in time polynomial in the input size and \(\frac{1}{\epsilon}\). For example, \(\frac{n^3}{\epsilon}\).
For maximization problems the \(1+\epsilon\) would be replaced with \(1-\epsilon\).
A problem is in APX ("approximable") if it has a constant-factor approximation algorithm. A problem is APX-Hard if it has no PTAS unless P=NP.

Q: Metric space
A: A metric space \(M,d\) is defined by a set of elements \(M\) with a metric \(d: M \times M \to \mathbb{R}_{\ge 0}\) with the following four properties:
1. \(d(x,x) = 0\) for all \(x \in M\): all points have distance 0 to themselves
2. If \(x \not= y\) then \(d(x,y) > 0\) (although this can be made arbitrarily small so often we allow a distance of 0)
3. \(d(x,y) = d(y,x)\) for all \(x,y \in M\)
4. \(d\) obeys the triangle inequality: \(d(x,z) \le d(x,y) + d(y,z)\) for all \(x,y,z \in M\).
A standard example of a metric space is Euclidean space, where points are tuples \((x_1,x_2) \in \mathbb{R}^2\) and \(d((x_1,x_2),(y_1,y_2)) = \sqrt{(x_1-y_1)^2 + (x_2-y_2)^2}\).

Q: Psuedopolynomial time
A: An algorithm runs in pseudopolynomial time if it runs in polynomial time in the input size when the numbers in the input are encoded in unary.

Q: Christofides' Algorithm for Metric TSP
A: As discussed in class, it's enough to find a multi-set of edges that connects the graph and has even degree at every vertex, as this edge set can always be "shortcut" to a Hamiltonian cycle of no greater cost.
Find a minimum spanning tree \(T\) of the graph: this gives connectivity. Then, compute the minimum cost perfect matching on the nodes with odd degree in \(T\): this makes all the vertices even degree.
This is a \(\frac{3}{2}\) approximation.

Q: Integrality Gap
A: The integrality gap of an ILP and its associated LP is the worst case ratio between the ILP OPT and the LP OPT over all instances.

Q: Integer Linear Program and Linear Program Relaxation
A: An Integer Linear Program (ILP) minimizes a linear objective function over a convex polyhedron \(P\). The variables are constrained to be integers. \[\begin{align*} \min c^Tx \\ x \in P \\ x \in \mathbb{Z}_{\ge 0}^n \end{align*}\]If we instead only constrain the variables to be real numbers, we get a Linear Program (LP):\[\begin{align*} \min c^Tx \\ x \in P \\ x \in \mathbb{R}_{\ge 0}^n \end{align*}\]Note we can flip min to max by negating the entries of \(c\), so these programs are fully general.
A natural extension is convex programs. Here we only need the feasible region to be a convex set and the objective function to be convex.

Q: Polyhedron and polytope and their matrix form
A: A polyhedron is the intersection of a finite number of halfspaces. A polytope is a bounded polyhedron.
We will typically write a polyhedron as the set of points \(x \in \mathbb{R}^n\) obeying the equations \(Ax \ge b\) for some matrix \(A \in \mathbb{R}^{m \times n}\) and vector \(b \in \mathbb{R}^m\). Each row of \(A\) represents one of the halfspaces of the polyhedron.

Q: Convex set
A: A set \(S \subseteq \mathbb{R}^d\) is convex if for any two points \(a,b \in S\) and any \(\alpha \in [0,1]\), the point \(\alpha a + (1-\alpha)b\) also lies in \(S\).
In this class, the primary example of a convex set will be a polyhedron: the intersection of finitely many half-spaces.

Q: Linear algebraic view of a vertex of a polyhedron
A: If \(v\) is a vertex of a polyhedron in \(n\) dimensions defined by half-spaces \(Ax \ge b\), then there is a matrix \(\tilde{A}\) consisting of \(n\) linearly independent rows of \(A\) so that \(v\) is the unique solution to the equation system \(\tilde{A}x = \tilde{b}\).
It is useful to notice that the subset of rows picked in \(\tilde{A}\) must be tight constraints.

Q: Relax and round framework
A: Start with an ILP whose feasible solutions are the feasible solutions for your optimization problem. Make sure the linear constraints of the ILP have a poly-time separation oracle. Then, relax the ILP to an LP, which is polynomial time solvable by the ellipsoid method. After solving this LP, round the resulting solution to a feasible integer solution, ideally without losing too much in cost (or whatever measure is of interest).
This can also be applied for more general convex programs.

Q: Ellipsoid method and separation oracle
A: Let \(P\) be a convex set. A separation oracle for \(P\) is a polynomial time procedure that given a point \(x \in \mathbb{R}^n\), either certifies that \(x \in P\) or returns a hyperplane that separates \(x\) from \(P\). In other words, it returns a vector \(a \in \mathbb{R}^n\) such that \(a^Tx > a^Ty\) for all \(y \in P\).
The ellipsoid method is a polynomial time algorithm that can optimize over any convex set with a separation oracle. (In other words, it can solve any LP whose feasible region is convex and has a separation oracle.)
In this course, \(P\) will typically be a convex polyhedron defined by a (possibly exponential size) collection of hyperplanes, and our separation oracle will return one of these hyperplanes.

Q: Minimum spanning tree
A: Given a graph \(G=(V,E)\) with weights \(w_e\) on the edges, a minimum spanning tree \(T\) is a spanning tree the the smallest possible weight \(\sum_{e \in T} w_e\).
A minimum spanning tree (MST) can be found using a greedy procedure called Kruskal's algorithm: keep adding the edge with the smallest weight to your MST as long as it does not create a cycle. Stop when every edge creates a cycle, at which point you must have a spanning tree if the original graph was connected.

Q: Carathéodory's Theorem
A: If \(x \in \mathbb{R}^n\) is a point in a polytope \(P\), then we can write \(x\) as a convex combination of at most \(n+1\) vertices \(v_1,\dots,v_{n+1}\) of \(P\).
In other words, we have \(x = \sum_{i=1}^{n+1} \lambda_i v_i\) where \(\sum_{i=1}^n \lambda_i = 1\) and \(\lambda_i \ge 0\) for all \(i\).

Q: Rank-Nullity Theorem
A: Given a matrix \(A \in \mathbb{R}^{m \times n}\),
\[\text{rank}(A) + \text{nullity}(A) = n\]where the rank of a matrix is the maximum number of linearly independent rows (or columns) and the nullity is the maximum number of linearly independent vectors \(x\) for which \(Ax=0\) (in other words, the rank of the null space of \(A\)).