`|= `@=

Applied Algorithms Anna Karlin, 426C Sieg
CSE 589, Autumn 2000

Homework # 5
Due 4pm, November 3

Reading: see slides

Problems

1.

Consider the following LP.

maximize  3x + 5y

subject to $x\le 4$, $2y \le 12$, $3x+2y \le 18$, $x,y \ge 0$.

• Draw the feasible set.
• Determine graphically the solution.
• Which vertices of the feasible set would the simplex algorithm visit en route to the solution?

2.

What is the dual problem of the following linear program?

maximize  4x+7y+2z

subject to $x+2y+z \le 10$, $2x+3y+3z \le 10$, $x,y,z \ge 0$.

3.

Prove that the subgraph isomorphism problem is NP-complete. In this problem, you are given two graphs G=(V₁,E₁) and H=(V₂,E₂), and you are asked if G contains a subgraph isomorphic to H, i.e., does there exist a subset $V\subseteq V_1$ and a subset $E\subseteq E_1$, such that (a) V and V₂ have the same size, (b) E and E₂ have the same size, and (c) there exists a one to one function $f:V_2 \rightarrow V$ satisfying $(u,v) \in E_2$ if and only if $(f(u),f(v)) \in E$?

4.

You are a traveling salesperson of the new millenium. Your boss has asked you to visit n cities, each exactly once, and you are planning your flight itinerary. You do not care about the cost of travel - the company is going to pay your expenses anyway. What you want to maximize is the benefits you will receive as a frequent flyer! In other words, you want to maximize the length of the entire trip. Do not worry about choosing different airlines. You just want to maximize the total mileage. Prove that this problem is NP-complete, and suggest heuristic approaches to it.

5.

Find, by either searching the web, searching the literature, or talking to people a real-life important problem that is NP-complete. It should not be one of the problems that's been mentioned in class. How is the problem solved in practice? (Either find out, or come up with your own idea.)

6.

Extra Credit Consider the following closest-point heuristic for building an approximate traveling-salesman tour. Begin with a trivial cycle consisting of a single arbitrarily chosen vertex. At each step, identify the vertex u that is not on the cycle but whose distance to any vertex on the cycle is minimum. Suppose that the vertex on the cycle that is nearest u is vertex v. Extend the cycle to include u by inserting u just after v. Repeat until all vertices are on the cycle. Prove that this heuristic returns a tour whose total cost is not more than twice the cost of an optimal tour.