2011-09-20
HW2 Problem 2.22.
Originally Posted By: jnewth
Showing that COMBINATORIAL AUCTION is in NP is simple.
Showing that COMBINATORIAL AUCTION is itself NPC is straightforward in principle (look at page 51, and read section 2.4).
I just want to make sure I understand the problem correctly. We have a set of items n. We have a whole bunch of possible sets Si which are subsets of n. Each subset Si has a value xi. A COMBINATORIAL AUCTION problem is one in which you are picking what sets to sell to earn at least k, with the provision that if, for example, item A appears in say S1, S6, S17, and S20, your solution can contain only one of S1, S6, S17 or S20, because an item can't be sold more than once. Is this correct?
Showing that COMBINATORIAL AUCTION is itself NPC is straightforward in principle (look at page 51, and read section 2.4).
I just want to make sure I understand the problem correctly. We have a set of items n. We have a whole bunch of possible sets Si which are subsets of n. Each subset Si has a value xi. A COMBINATORIAL AUCTION problem is one in which you are picking what sets to sell to earn at least k, with the provision that if, for example, item A appears in say S1, S6, S17, and S20, your solution can contain only one of S1, S6, S17 or S20, because an item can't be sold more than once. Is this correct?
'''Originally Posted By: jnewth'''
Showing that COMBINATORIAL AUCTION is in NP is simple.<br><br>Showing that COMBINATORIAL AUCTION is itself NPC is straightforward in principle (look at page 51, and read section 2.4).<br><br>I just want to make sure I understand the problem correctly. We have a set of items n. We have a whole bunch of possible sets Si which are subsets of n. Each subset Si has a value xi. A COMBINATORIAL AUCTION problem is one in which you are picking what sets to sell to earn at least k, with the provision that if, for example, item A appears in say S1, S6, S17, and S20, your solution can contain only one of S1, S6, S17 or S20, because an item can't be sold more than once. Is this correct?
Originally Posted By: jnewth
I am hoping the professor can give me a hint on this one.
I am having trouble converting an instance of the SAT problem in to an instance of the COMBINATORIAL AUCTION problem. The reason is that I can't figure out how to convert the CNF clauses in to Sets.
I can imagine generating for each clause of the CNF phrase some boolean assignments that allow that clause to be true. These could all be assigned a value of x="1", and all failing solutions be given a value of x="0". Then k might be the number of clauses in the original phrase. Then, if you grab a solution S to each clause of the phrase, you get your sum equal to K. The problem is that we need to make sure that a potential solution for the COMBINATORIAL AUCTION problem is to grab up all the Sets that produce 1 for a single clause to increase the score without yielding a solution. We also want to disallow any selection of two sets where one requires a term to be true and the other requires the same term to be false.
We want any collection of sets selected as a solution to our COMBINATORIAL AUCTION to be a set of assignments that solve the SAT problem.
I am having trouble converting an instance of the SAT problem in to an instance of the COMBINATORIAL AUCTION problem. The reason is that I can't figure out how to convert the CNF clauses in to Sets.
I can imagine generating for each clause of the CNF phrase some boolean assignments that allow that clause to be true. These could all be assigned a value of x="1", and all failing solutions be given a value of x="0". Then k might be the number of clauses in the original phrase. Then, if you grab a solution S to each clause of the phrase, you get your sum equal to K. The problem is that we need to make sure that a potential solution for the COMBINATORIAL AUCTION problem is to grab up all the Sets that produce 1 for a single clause to increase the score without yielding a solution. We also want to disallow any selection of two sets where one requires a term to be true and the other requires the same term to be false.
We want any collection of sets selected as a solution to our COMBINATORIAL AUCTION to be a set of assignments that solve the SAT problem.
'''Originally Posted By: jnewth'''
I am hoping the professor can give me a hint on this one. <br>I am having trouble converting an instance of the SAT problem in to an instance of the COMBINATORIAL AUCTION problem. The reason is that I can't figure out how to convert the CNF clauses in to Sets. <br><br>I can imagine generating for each clause of the CNF phrase some boolean assignments that allow that clause to be true. These could all be assigned a value of x="1", and all failing solutions be given a value of x="0". Then k might be the number of clauses in the original phrase. Then, if you grab a solution S to each clause of the phrase, you get your sum equal to K. The problem is that we need to make sure that a potential solution for the COMBINATORIAL AUCTION problem is to grab up all the Sets that produce 1 for a single clause to increase the score without yielding a solution. We also want to disallow any selection of two sets where one requires a term to be true and the other requires the same term to be false.<br><br>We want any collection of sets selected as a solution to our COMBINATORIAL AUCTION to be a set of assignments that solve the SAT problem.
jnewth wrote:
Showing that COMBINATORIAL AUCTION is in NP is simple.
Showing that COMBINATORIAL AUCTION is itself NPC is straightforward in principle (look at page 51, and read section 2.4).
I just want to make sure I understand the problem correctly. We have a set of items n. We have a whole bunch of possible sets Si which are subsets of n. Each subset Si has a value xi. A COMBINATORIAL AUCTION problem is one in which you are picking what sets to sell to earn at least k, with the provision that if, for example, item A appears in say S1, S6, S17, and S20, your solution can contain only one of S1, S6, S17 or S20, because an item can't be sold more than once. Is this correct?
Yes.
It seems like you were on the right track with respect to the second thing you wrote.
Showing that COMBINATORIAL AUCTION is in NP is simple.
Showing that COMBINATORIAL AUCTION is itself NPC is straightforward in principle (look at page 51, and read section 2.4).
I just want to make sure I understand the problem correctly. We have a set of items n. We have a whole bunch of possible sets Si which are subsets of n. Each subset Si has a value xi. A COMBINATORIAL AUCTION problem is one in which you are picking what sets to sell to earn at least k, with the provision that if, for example, item A appears in say S1, S6, S17, and S20, your solution can contain only one of S1, S6, S17 or S20, because an item can't be sold more than once. Is this correct?
Yes.
It seems like you were on the right track with respect to the second thing you wrote.
jnewth wrote:<br>Showing that COMBINATORIAL AUCTION is in NP is simple.<br><br>Showing that COMBINATORIAL AUCTION is itself NPC is straightforward in principle (look at page 51, and read section 2.4).<br><br>I just want to make sure I understand the problem correctly. We have a set of items n. We have a whole bunch of possible sets Si which are subsets of n. Each subset Si has a value xi. A COMBINATORIAL AUCTION problem is one in which you are picking what sets to sell to earn at least k, with the provision that if, for example, item A appears in say S1, S6, S17, and S20, your solution can contain only one of S1, S6, S17 or S20, because an item can't be sold more than once. Is this correct?<br><br><br>Yes.<br><br>It seems like you were on the right track with respect to the second thing you wrote.
(c) 2024 Yioop - PHP Search Engine