COMS 482: unofficial class blog

Prelim II is next Tuesday. The announcement isn’t on the course website yet, but here are review questions from 2000 spring, for the eager:

1. You are given a graph G = (V, E) with weights w_e on its edges {e in E}. The weights can be negative or positive. The Zero-­weight-cycle problem is to decide if there is a simple cycle in G so that the sum of the edge weights on this cycle is exactly 0.

   Prove that this problem is NP­complete.

2. Since the 3­Dimensional Matching problem is NP­complete, it is natural to expect that the corresponding 4­Dimensional Matching problem is at least as hard. Let us define 4­Dimensional Matching as follows. Given sets W , X , Y , and Z, each of size n, and a collection C of ordered 4­tuples of the form (w_i , x_j, y_k, z_l), do there exist n 4-­tuples from C so that no two have an element in common?

   Prove that 4­Dimensional Matching is NP­complete.

3. Some of your friends have recently graduated and started a small company called WebExodus, which they are currently running out of their parents’ garages in Santa Clara. They’re in the process of porting all their software from an old system to a new, revved­up system; and they’re facing the following problem.

   They have a collection of n software applications, {1, 2, . . . , n}, running on their old system; and they’d like to port some of these to the new system. If they move application i to the new system, they expect a net (monetary) benefit of b_i >= 0. The different software applications interact with one another; if applications i and j have extensive interaction, then the company will incur an expense if they move one of i or j to the new system but not both — let’s denote this expense by x_i,j >= 0.

   So if the situation were really this simple, your friends would just port all n applications, achieving a total benefit of sum(b_i . Unfortunately, there’s a problem . . . Due to small but fundamental incompatibilities between the two systems, there’s no way to port application 1 to the new system; it will have to remain on the old system. Nevertheless, it might still pay to port some of the other applications, accruing the associated benefit and incurring the expense of the interaction between applications on different systems.

   So this is the question they pose to you: which of the remaining applications, if any, should be moved? Give a polynomial­ time algorithm to find a set S # {2, 3, . . . , n} for which the sum of the benefits minus the expenses of moving the applications in S to the new system is maximized.

Update:

New review problems have been posted here: www.cs.cornell.edu/courses/cs482/2005sp/review2.htm

This entry was posted on Sunday, April 10th, 2005 at 12:08 pm and is tagged with edge weights, port application, zero weight, collection c, prelim, tuples, incompatibilities, yk, software applications, garages, santa clara, graph, interaction, element, benefit, parents. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback.

Leave a Reply

Name (required)

Mail (will not be published) (required)

Website

I'll protect you: the flagrant and fair Wordpress Anti-Spam Plugin?

Please take time to enjoy the archives: May 2005 (1) April 2005 (11) March 2005 (11) February 2005 (15) January 2005 (7)

Fresh, related resources: