Talk:CS 6963 Summaries

From ResearchWiki

(Difference between revisions)
Jump to: navigation, search
(→28 Aug)
(→28 Aug)
Line 16: Line 16:
: In the analysis of the Las Vegas algorithm for the coloring problem (or, in general, any other Las Vegas algorithm), is it possible to prove the algorithm ''always'' completes in polynomial time, or can we simply prove that it completes in polynomial time ''with high probability''? (For example, we can imagine that there is only one value for the random variable(s) that leads the algorithm to find a correct solution, but a truly random distribution is not ''guaranteed'' to return that value within a particular (finite) number of trials - it's just ''probable'' that it will.)
: In the analysis of the Las Vegas algorithm for the coloring problem (or, in general, any other Las Vegas algorithm), is it possible to prove the algorithm ''always'' completes in polynomial time, or can we simply prove that it completes in polynomial time ''with high probability''? (For example, we can imagine that there is only one value for the random variable(s) that leads the algorithm to find a correct solution, but a truly random distribution is not ''guaranteed'' to return that value within a particular (finite) number of trials - it's just ''probable'' that it will.)
::(Piyush) The Las Vegas algorithm assumes conditions (i.e. sample size and the verification algorithm both should be polynomial in the problem size) that, in polynomial time, guarantee a correct solution or the non-existence of such a solution. If the assumed conditions are not met, you cannot have a Las Vegas algorithm for the problem. In your case, the sample size clearly is not polynomial in the problem size. So, by definition, it cannot be called a Las Vegas algorithm.
::(Piyush) The Las Vegas algorithm assumes conditions (i.e. sample size and the verification algorithm both should be polynomial in the problem size) that, in polynomial time, guarantee a correct solution or the non-existence of such a solution. If the assumed conditions are not met, you cannot have a Las Vegas algorithm for the problem. In your case, the sample size clearly is not polynomial in the problem size. So, by definition, it cannot be called a Las Vegas algorithm.
-
 
'''Tilottama'''
'''Tilottama'''
:I have a general question -While choosing to apply either the Counting Argument or the Expectation Argument, is there any intuition as to which method is more suited to a particular problem?
:I have a general question -While choosing to apply either the Counting Argument or the Expectation Argument, is there any intuition as to which method is more suited to a particular problem?
 +
::(Piyush):
 +
In general, it depends on the problem. Note that the object in consideration is a random variable. If it is possible to express the desired properties as some expected value depending on this random variable, the expectation argument might be preferred. Such were the cases, for example, with the max-cut and maxsat problems.
'''Parasaran'''  
'''Parasaran'''  
Given a NP-Hard problem, what tells an algorithm analyst to choose the Randomization (Probabilistic method) or Derandomization (Deterministic Method)?
Given a NP-Hard problem, what tells an algorithm analyst to choose the Randomization (Probabilistic method) or Derandomization (Deterministic Method)?
 +
::(Piyush): It depends on the problem structure. If the correctness or feasibility of a randomized algorithm is not satisfactory, one may try derandomization. But whether you can derandomize an randomized algorithm may or may not be possible, again depending on the problem.
In the 'Sample and Modify' Example-1, how do we choose the average degree of the vertex (d) to be 2m/n ?
In the 'Sample and Modify' Example-1, how do we choose the average degree of the vertex (d) to be 2m/n ?
 +
::(Piyush): Each edge is shared between two vertices. Thus the sum of degrees would be 2m. Since there are n vertices, we get an average 2m/n.
'''Avishek'''  
'''Avishek'''  
As we have seen, existential proofs using probabilistic methods can be converted into efficient randomized or deterministic construction algorithms. Although I am not sure, I guess there might be situations/cases where this conversion is not possible.  
As we have seen, existential proofs using probabilistic methods can be converted into efficient randomized or deterministic construction algorithms. Although I am not sure, I guess there might be situations/cases where this conversion is not possible.  
 +
::(Piyush): Yes, there can be situations where a randomized algorithm may not be able to give a satisfactory solution (in term of correctness or feasibility) or a derandomized construction is not possible.
: If this is true, then can we in some manner infer from the probabilistic method whether it would be able to give rise to some (randomized or deterministic) construction algorithm or nothing at all ?
: If this is true, then can we in some manner infer from the probabilistic method whether it would be able to give rise to some (randomized or deterministic) construction algorithm or nothing at all ?
 +
:::(Piyush): If you construct a Monte Carlo algorithm, the success will depend on the probability of getting the correct sample. In you construct a Las Vegas algorithm, it would depend on being able to efficiently sample a candidate solution, sample size, and the time to check whether the solution is correct or not (these values should be polynomial in problem size in order to give a satisfactory solution). Note, however, that some probabilistic methods (such as sample and modify), give us a randomized algorithm as a byproduct of the existence proof itself.
'''Hal'''
'''Hal'''
:I don't follow the "sample and modify" algorithm for independent sets.  In particular, I don't see why it holds that the vertices obtained by the algorithm form an independent set.
:I don't follow the "sample and modify" algorithm for independent sets.  In particular, I don't see why it holds that the vertices obtained by the algorithm form an independent set.
-
 
+
::(Piyush): In both the steps, by construction (or "destruction"), we are removing one of the two vertices that connected by an edge. So at the end, we will never have a vertex pair that was connected originally. And since we end up removing all the edges at the end of step-2, the set of vertices we are left with forms an independent set.
'''Arvind'''
'''Arvind'''
:I don't understand the step 2 of the "sample and modify" algorithm for independent set.
:I don't understand the step 2 of the "sample and modify" algorithm for independent set.
 +
::(Piyush): By deleting an edge (and one of the associated vertices), step-2 just removes one vertex from each pair of vertices that are connected (and hence could never be in an independent set together). This (combined with step-1) leaves us only with a set of vertices that were not connected in the beginning.

Revision as of 15:54, 28 August 2008

28 Aug

Nathan

Is it possible for objects in your chosen probability space S to have a zero probability, or do all objects in S contain the properties desired for your application?
(Piyush): For the former question, the answer, in principle, is yes. But usually the probability space S is constructed appropriately by posing certain restrictions on it so that we end up getting a non-zero probability of existence. These restrictions, however, would usually be reasonable ones. For example, in the monochromatic subgraph problem, we assume that {n\choose k}2^{-{k \choose 2} + 1} < 1, which would indeed be a reasonable assumption for many problem instances. On the other hand, for the latter question, it would be highly unlikely (and probably uninteresting) to have a case when all objects in S have the desirable properties.

Scott

In section 6.4.2, when it says " G \in G_{n, p}", what does the notion "Gn,p" mean?
(Piyush): Gn,p is a random graph with n nodes that probability p of having an edge between any two nodes.

Amit

I am not able to convince myself the max cut size be at least m/2. I buy the later argument that we need at most m/2 +1 samples to find a cut with at least m/2 edges.
(Piyush) Note that the probability that an edge ei connects a vertex in A to a vertex in B is 1/2. To see this, consider both vertices (say v1 and v2) associated with ei. Since we are assigning v1 and v2 to sets A or B randomly and independently, the probability that they go to different sets (i.e. one to A and the other to B) is 1/2. If it is still unclear, think of this: you can assign the first vertex to any of the sets (say A) with probability 1. But then you must assign the second vertex to the other set (B), with probability 1/2. Since these two events are independent, we get an overall probability of 1/2. Invoking the linearity of expectation argument, we get the m/2 lower bound on the max cut size.

Rob

In the analysis of the Las Vegas algorithm for the coloring problem (or, in general, any other Las Vegas algorithm), is it possible to prove the algorithm always completes in polynomial time, or can we simply prove that it completes in polynomial time with high probability? (For example, we can imagine that there is only one value for the random variable(s) that leads the algorithm to find a correct solution, but a truly random distribution is not guaranteed to return that value within a particular (finite) number of trials - it's just probable that it will.)
(Piyush) The Las Vegas algorithm assumes conditions (i.e. sample size and the verification algorithm both should be polynomial in the problem size) that, in polynomial time, guarantee a correct solution or the non-existence of such a solution. If the assumed conditions are not met, you cannot have a Las Vegas algorithm for the problem. In your case, the sample size clearly is not polynomial in the problem size. So, by definition, it cannot be called a Las Vegas algorithm.

Tilottama

I have a general question -While choosing to apply either the Counting Argument or the Expectation Argument, is there any intuition as to which method is more suited to a particular problem?
(Piyush):

In general, it depends on the problem. Note that the object in consideration is a random variable. If it is possible to express the desired properties as some expected value depending on this random variable, the expectation argument might be preferred. Such were the cases, for example, with the max-cut and maxsat problems.

Parasaran

Given a NP-Hard problem, what tells an algorithm analyst to choose the Randomization (Probabilistic method) or Derandomization (Deterministic Method)?

(Piyush): It depends on the problem structure. If the correctness or feasibility of a randomized algorithm is not satisfactory, one may try derandomization. But whether you can derandomize an randomized algorithm may or may not be possible, again depending on the problem.

In the 'Sample and Modify' Example-1, how do we choose the average degree of the vertex (d) to be 2m/n ?

(Piyush): Each edge is shared between two vertices. Thus the sum of degrees would be 2m. Since there are n vertices, we get an average 2m/n.

Avishek

As we have seen, existential proofs using probabilistic methods can be converted into efficient randomized or deterministic construction algorithms. Although I am not sure, I guess there might be situations/cases where this conversion is not possible.

(Piyush): Yes, there can be situations where a randomized algorithm may not be able to give a satisfactory solution (in term of correctness or feasibility) or a derandomized construction is not possible.
If this is true, then can we in some manner infer from the probabilistic method whether it would be able to give rise to some (randomized or deterministic) construction algorithm or nothing at all ?
(Piyush): If you construct a Monte Carlo algorithm, the success will depend on the probability of getting the correct sample. In you construct a Las Vegas algorithm, it would depend on being able to efficiently sample a candidate solution, sample size, and the time to check whether the solution is correct or not (these values should be polynomial in problem size in order to give a satisfactory solution). Note, however, that some probabilistic methods (such as sample and modify), give us a randomized algorithm as a byproduct of the existence proof itself.

Hal

I don't follow the "sample and modify" algorithm for independent sets. In particular, I don't see why it holds that the vertices obtained by the algorithm form an independent set.
(Piyush): In both the steps, by construction (or "destruction"), we are removing one of the two vertices that connected by an edge. So at the end, we will never have a vertex pair that was connected originally. And since we end up removing all the edges at the end of step-2, the set of vertices we are left with forms an independent set.

Arvind

I don't understand the step 2 of the "sample and modify" algorithm for independent set.
(Piyush): By deleting an edge (and one of the associated vertices), step-2 just removes one vertex from each pair of vertices that are connected (and hence could never be in an independent set together). This (combined with step-1) leaves us only with a set of vertices that were not connected in the beginning.
Retrieved from "http://www.cs.utah.edu/~suresh/mediawiki/index.php/Talk:CS_6963_Summaries"
Personal tools