Approximation Algorithms


steiner_tree

In the node-weighted Steiner tree problem, we are given as input an undirected graph G=(V,E)G = (V, E), node weights wi0w_i \geq 0 for all iVi \in V, edge costs ce0c_e \geq 0 for all eEe \in E, and a set of terminals TVT \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 TT.

  1. Show that there exists some cc such that there is no (clnT)(c \ln T)-approximation algorithm for the node-weighted Steiner tree problem unless P = NP.
  2. Give a greedy O(lnT)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)G = (V, A) with costs cij0c_{ij} \geq 0 for all arcs (i,j)A(i, j) \in A, such that the arc costs obey the triangle inequality: for all i,j,kVi,j,k \in V, we have that cij+cjkcikc_{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,jVi,j \in V there is a path from ii to jj and a path from jj to ii. 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 2Hn2H_n \cdotOPT, where n=Vn = |V| and OPT is the cost of the optimal tour. Conclude that this algorithm is a 2Hn2H_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

miniVwixis.t(i,j)Exi+xj1iVxi0 \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 xi{0,12,1}x_i \in \{0, \frac{1}{2}, 1\} for all iVi \in V. (Recall that an extreme point xx is a feasible solution that cannot be expressed as λx1+(1λ)x2\lambda x^1 + (1 - \lambda)x^2 for 0<λ<10 < \lambda < 1 and feasible solutions x1x^1 and x2x^2 distinct from xx.)

2. Give a 32\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)E(i, j) \in E, vertices ii and jj 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, kk, and a set of vertices VV, along with distances dijd_{ij} between any two vertices, i,ji,j that obey the same properties as in the k-center problem. However, now the vertices are partitioned into suppliers FVF \subseteq V and customers D=VFD = V \setminus F. The goal is to find kk suppliers such that the maximum distance from a supplier to a customer is minimized. In other words, we wish to find SF,SkS \subseteq F, |S| \leq k, that minimizes maxjDd(j,S)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 α<3\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 II that minimizes jIwj\sum_{j \in I} w_j such that

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

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

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

where 0<p<10 < 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)c(p) \cdotOPT, where c(p)c(p) is a constant that depends on pp, and OPT is the value of the optimal solution to the set cover problem.
  2. Give an f(p)f(p)-approximation algorithm for the partial cover problem, such that ff is non-decreasing in pp and f(1)HEf(1) \leq H_{E}.
directed_steiner
hardness

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

Prove that for some constant cc there can be no clogTc\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 DD and a set of facilities FF. For each client jDj \in D and facility iFi \in F, there is a cost cijc_{ij} of assigning client jj to facility ii. Furthermore, there is a cost fif_i associated with each facility iFi \in F. The goal of the problem is to choose a subset of facilities FFF' \subseteq F so as to minimize the total cost of the facilities in FF' and the cost of assigning each client jDj \in D to the nearest facility in FF'. In other words, we wish to find FF' so as to minimize iFfi+jDminiFcij\sum_{i \in F'} f_i + \sum_{j \in D}\min_{i \in F}c_{ij}.

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