Tag Archives: Partition

Cosine Product Integration

I’m back from break, and we’ll go a little out of order at first since this is the last problem that’s similar to the ones we’ve been working on.

The problem: Cosine Product Integration.  This is problem AN14 in the appendix.

The description: Given a sequence of n integers (a_i..a_n), does \displaystyle \int_0^{2\Pi} (\prod_{i=1}^n cos(a_i\theta)) d\theta = 0?

Example:

Suppose our sequence was (1,2,3).  Then our integral is:

\displaystyle \int_o^{2\Pi}(\theta*2\theta*3\theta)d\theta

This is just 6\theta^3, which integrates to \frac{6x^4}{4}, which over the interval 0..2\pi is 24\pi^4

Reduction: This one is in Plaisted’s 1976 paper. In it, he notes that if you look at the function \displaystyle \prod_{j=1}^{k} (x^{a_j}+x^{-a_j}) the constant term in the power series expansion of that product is 0 if and only if the cosine integral is 0.  I have trouble seeing that myself.  The cooler thing is that you can make that constant term 0 if and only if you can take the sequence of a_i elements and partition them into 2 sets with the same sum.  So we can take an instance of the Partition problem, use the elements of the set as the elements of our sequence and then feed them into the product formulas.

Difficulty: It really depends on how easily you can see the connection between the cosine integral and the product formula (and, of course, how easily you could have thought of it). I find it hard, so I’m giving it an 8.

Protected: Open-Shop Scheduling

This content is password protected. To view it please enter your password below:

Protected: Scheduling to Minimize Weighted Completion Time

This content is password protected. To view it please enter your password below:

Protected: Sequencing to Minimize Tardy Tasks, Sequencing to Minimize Tardy Task Weight

This content is password protected. To view it please enter your password below:

Protected: Sequencing With Release Times and Deadlines

This content is password protected. To view it please enter your password below:

Protected: Expected Retrieval Cost

This content is password protected. To view it please enter your password below:

Protected: Kth Largest m-Tuple

This content is password protected. To view it please enter your password below:

Protected: Subset Product

This content is password protected. To view it please enter your password below: