# Approximation Algorithms

steiner_tree

In the node-weighted Steiner tree problem, we are given as input an undirected graph $G = (V, E)$, node weights $w_i \geq 0$ for all $i \in V$, edge costs $c_e \geq 0$ for all $e \in E$, and a set of terminals $T \subseteq V$. The cost of a tree is the sum of the weights of the nodes plus the sum of the costs of the edges in the tree. The goal of the problem is to find a minimum-weight tree that spans all the terminals in $T$.

1. Show that there exists some $c$ such that there is no $(c \ln T)$-approximation algorithm for the node-weighted Steiner tree problem unless P = NP.
2. Give a greedy $O(\ln T)$-approximation algorithm for the node-weighted Steiner tree problem.
asymmetric_tsp

In the metric asymmetric traveling salesman problem, we are given as input a complete directed graph $G = (V, A)$ with costs $c_{ij} \geq 0$ for all arcs $(i, j) \in A$, such that the arc costs obey the triangle inequality: for all $i,j,k \in V$, we have that $c_{ij} + c_{jk} \geq c_{ik}$. The goal is to find a tour of minimum cost, that is, a directed cycle that contains each vertex exactly once, such that the sum of the cost of the arcs in the cycle is minimized.

One approach to finding an approximation algorithm for this problem is to first find a minimum-cost strongly connected Eulerian subgraph of the input graph. A directed graph is strongly connected if for any pair of vertices $i,j \in V$ there is a path from $i$ to $j$ and a path from $j$ to $i$. A directed graph is Eulerian if the indegree of each vertex equals its outdegree. Given a strongly connected Eulerian subgraph of the input to the problem, it is possible to use a technique called "shortcutting" to turn this into a tour of no greater cost by using the triangle inequality.

One way to find a strongly connected Eulerian subgraph is as follows: We first find a minimum mean-cost cycle in the graph. A minimum mean-cost cycle is a directed cycle that minimizes the ratio of the cost of the arcs in the cycle to the number of arcs in the cycle. Such a cycle can be found in polynomial time. We then choose one vertex of the cycle arbitrarily, remove all other vertices of the cycle from the graph, and repeat. We do this until only one vertex of the graph is left. Consider the subgraph consisting of all the arcs from all the cycles found.

1. Prove that the subgraph found by the algorithm is a strongly connected Eulerian subgraph of the input graph.
2. Prove that the cost of this subgraph is at most $2H_n \cdot$OPT, where $n = |V|$ and OPT is the cost of the optimal tour. Conclude that this algorithm is a $2H_n$-approximation algorithm for the metric asymmetric traveling salesman problem.
vertex_cover
extream_point

Consider the vertex cover problem.

1. Prove that any extreme point of the linear program

$\begin{array}{ll} \min & \sum_{i \in V}w_ix_i \\ \text{s.t} \\ \forall (i, j) \in E & x_i + x_j \geq 1 \\ \forall i \in V & x_i \geq 0 \end{array}$

has the property that $x_i \in \{0, \frac{1}{2}, 1\}$ for all $i \in V$. (Recall that an extreme point $x$ is a feasible solution that cannot be expressed as $\lambda x^1 + (1 - \lambda)x^2$ for $0 < \lambda < 1$ and feasible solutions $x^1$ and $x^2$ distinct from $x$.)

2. Give a $\frac{3}{2}$-approximation algorithm for the vertex cover problem when the input graph is planar. You may use the facts that polynomial-time LP solvers return extreme points, and that there is a polynomial-time algorithm to 4-color any planar graph (i.e. the algorithm assigns each vertex one of four colors such that for any edge $(i, j) \in E$, vertices $i$ and $j$ have been assigned different colors).

greedy
hardness
k-center
k-suppliers

The k-suppliers problem is similar to the k-center problem. The input to the problem is a positive integer, $k$, and a set of vertices $V$, along with distances $d_{ij}$ between any two vertices, $i,j$ that obey the same properties as in the k-center problem. However, now the vertices are partitioned into suppliers $F \subseteq V$ and customers $D = V \setminus F$. The goal is to find $k$ suppliers such that the maximum distance from a supplier to a customer is minimized. In other words, we wish to find $S \subseteq F, |S| \leq k$, that minimizes $max_{j \in D}d(j, S)$.

1. Give a 3-approximation algorithm for the k-suppliers problem.
2. Prove that there is no $\alpha$-approximation algorithm for $\alpha < 3$ unless P = NP.
set_cover
randomize_rounding

In the set cover problem, the goal is to find a collection of subsets indexed by $I$ that minimizes $\sum_{j \in I} w_j$ such that

$\left| \bigcup_{j \in I} S_j \right| = |E|.$

Consider the partial cover problem, in which one finds a collection of subset indexed by $I$ that minimizes $\sum_{j \in I} w_j$ such that

$\left| \bigcup_{j \in I} S_j \right| = p|E|.$

where $0 < p < 1$ is some constant.

1. Give a polynomial-time algorithm to find a solution to the partial cover problem in which the value is no more than $c(p) \cdot$OPT, where $c(p)$ is a constant that depends on $p$, and OPT is the value of the optimal solution to the set cover problem.
2. Give an $f(p)$-approximation algorithm for the partial cover problem, such that $f$ is non-decreasing in $p$ and $f(1) \leq H_{E}$.
directed_steiner
hardness

In the directed Steiner tree problem, we are given as input a directed graph $G = (V, A)$, non-negative costs $c_{ij} \geq 0$ for arcs $(i, j) \in A$, a root vertex $r \in V$, and a set of terminals $T \subseteq V$. The goal is to find a minimum-cost tree such that for each $i \in T$ there exists a directed path from $r$ to $i$.

Prove that for some constant $c$ there can be no $c\log |T|$-approximation algorithm for the directed Steiner tree problem, unless P = NP.

set_cover
facility_location

In the uncapacitated facility location problem, we have a set of clients $D$ and a set of facilities $F$. For each client $j \in D$ and facility $i \in F$, there is a cost $c_{ij}$ of assigning client $j$ to facility $i$. Furthermore, there is a cost $f_i$ associated with each facility $i \in F$. The goal of the problem is to choose a subset of facilities $F' \subseteq F$ so as to minimize the total cost of the facilities in $F'$ and the cost of assigning each client $j \in D$ to the nearest facility in $F'$. In other words, we wish to find $F'$ so as to minimize $\sum_{i \in F'} f_i + \sum_{j \in D}\min_{i \in F}c_{ij}$.

1. Show that there exists some $c$ such that there is no $(c \ln |D|)$-approximation algorithm for the uncapacitated facility location problem unless P = NP.
2. Give an $O(\ln |D|)$-approximation algorithm for the uncapacitated facility location problem.
Feedback