Homework #2

Homework #2 (and exercises) now on the webpage.  It’s due in a week, i.e., next Thursday (9/29). And again, ask questions and make comments on the homework in the comments below.

Clarification: for problem #3, feel free to use the result of Hwk2(#1) that we can reduce the search version of feasibility to the decision version.

Advertisements

3 Comments to “Homework #2”

  1. I think the first part of problem 5 seems to leave open using an LP formulation for which I don’t see a better value than OPT. IE, rather than letting the clause’s value be bounded by some sum of variables, what if they’re bounded by a max of sum variables? Then I’m thinking that I don’t have the right LP for what you want… there are obviously several LP formulations of MAX-SAT with 1 variable/clause and 1 variable/ variable.

    I figured out the one you want, but I think it might be wise to be slightly more specific. In the case that your clause variables are equal to a max of things, you won’t have the problem that you’ll ever have a setting of variables which set your clause value to 1 unless a variable is set to 1.

  2. Hi Jamie. If you think you have an LP formulation of the Max-Sat problem with the property that LPOpt = Opt, then I guess you probably don’t… Max-Sat is NP-hard so this would show NP = P. Maybe you should double-check that the formulation you have can really be expressed an LP: optimizing a linear function subject to linear inequalities…

  3. My LP formulation didn’t have LPOPT = OPT, it did have the property that you couldn’t (with 4 clauses) get a full integer larger value for LPOPT, since each clause variable was taking on a max of things in [0,1] rather than a sum of variables in [0,1] (thus, any clause variable would be 1 iff one of the variables were set to 1).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: