User charles bailey - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T19:21:58Z http://mathoverflow.net/feeds/user/19481 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/94992/p-version-of-subset-sum #P version of SUBSET SUM Charles Bailey 2012-04-24T02:22:29Z 2012-05-22T22:22:01Z <p>The decision version of the SUBSET SUM problem asks the following: Given a set of integers $S =$ {$a_1, ..., a_n$}, is there a subset $S'$ of $S$ such that the sum of the elements in $S'$ is equal to zero. This problem is NP-complete.</p> <p>The corresponding #P problem asks HOW MANY subsets of $S$ sum to zero. </p> <p>Does anyone know of a pseudo-polynomial time algorithm for solving this enumeration version of the problem? It seems that it would have to be polynomial in the number of elements in S, the size of the elements in S, and the number of subsets that sum to zero. Beyond that, I don't know what the algorithm would look like. Perhaps a simple dynamic programming solution exists, but I'm not sure what it is.</p> <p>Thanks, Charles</p> http://mathoverflow.net/questions/90927/shortest-absolute-value-of-path-in-graph Shortest absolute value of path in graph Charles Bailey 2012-03-11T19:45:14Z 2012-03-12T04:10:40Z <p>Suppose we have a weighted, acyclic digraph, with positive and negative edge weights.</p> <p>Is there an algorithm that determines whether there is a path of weight zero between vertices A and B? The Bellman-Form algorithm finds the path of smallest weight - is there another algorithm that determines the path of smallest absolute value weight?</p> <p>Thanks, Charles</p> http://mathoverflow.net/questions/81741/approximate-action-of-unitary-matrix-with-permutation-matrix Approximate action of unitary matrix with permutation matrix Charles Bailey 2011-11-23T19:13:47Z 2011-11-23T20:02:30Z <p>Given a unitary matrix Q and a symmetric matrix B, I am trying to find a permutation matrix P such that </p> <p>$|| QBQ^{T} - PBP^{T} ||_{F}$ </p> <p>is minimized. </p> <p>The straightforward method of minimizing $|| Q - P ||_{F}$ does not work. </p> <p>I was wondering if there would be some way to orthogonally project the orbit of B under conjugation by unitary matrices onto the orbit of B under conjugation by permutation matrices. I don't know precisely how that would work though. </p> <p>Does anyone have any suggestions? </p> <p>Thanks,</p> <p>Charles</p> <p>Edit:</p> <p>An example that shows that minimizing $||Q-P||_{F}$ does not work is as follows:</p> <p>B = \begin{array}{cc} 0 &amp; 1 &amp; 1 &amp; 1 \newline 1 &amp; 0 &amp; 0 &amp; 0 \newline 1 &amp; 0 &amp; 0 &amp; 0 \newline 1 &amp; 0 &amp; 0 &amp; 0 \newline \end{array}</p> <p>Q =<br> \begin{array}{rr} -0.6544 &amp; -0.6544 &amp; 0.1585 &amp; 0.3440 \newline -0.0473 &amp; -0.0473 &amp; -0.9624 &amp; 0.2633 \newline -0.6864 &amp; 0.3136 &amp; -0.1561 &amp; -0.6373 \newline 0.3136 &amp; -0.6864 &amp; -0.1561 &amp; -0.6373 \newline \end{array}</p> <p>$P_{1}$ = \begin{array}{rr} 0 &amp; 0 &amp; 1&amp; 0 \newline 0 &amp; 0 &amp; 0 &amp; 1 \newline 0 &amp; 1 &amp; 0 &amp; 0 \newline 1 &amp; 0 &amp; 0 &amp; 0 \newline \end{array}</p> <p>$P_{2}$ = \begin{array}{rr} 1&amp; 0&amp; 0 &amp; 0\newline 0 &amp; 0 &amp; 1 &amp; 0\newline 0 &amp; 1 &amp; 0 &amp; 0\newline 0 &amp; 0 &amp; 0 &amp; 1\newline \end{array}</p> <p>With these matrices,</p> <p>\begin{align} || Q - P_{1} || &amp;&lt; || Q - P_{2} || \end{align}</p> <p>but \begin{align} || QBQ^{T} - P_{1}BP_{1}^{T} || &amp;> || QBQ^{T} - P_{2}BP_{1}^{T} || \end{align}</p> http://mathoverflow.net/questions/94992/p-version-of-subset-sum Comment by Charles Bailey Charles Bailey 2012-04-24T19:05:09Z 2012-04-24T19:05:09Z By size of the element, I mean their absolute values. - Charles http://mathoverflow.net/questions/90927/shortest-absolute-value-of-path-in-graph Comment by Charles Bailey Charles Bailey 2012-03-12T02:55:07Z 2012-03-12T02:55:07Z Yes, it's a finite graph, so exhaustive search would work. I'm looking for something more efficient. Thanks, Charles http://mathoverflow.net/questions/90927/shortest-absolute-value-of-path-in-graph Comment by Charles Bailey Charles Bailey 2012-03-11T20:23:43Z 2012-03-11T20:23:43Z The weights are integers in the interval [-c,c] for some integer constant c. http://mathoverflow.net/questions/81741/approximate-action-of-unitary-matrix-with-permutation-matrix Comment by Charles Bailey Charles Bailey 2011-11-24T01:28:59Z 2011-11-24T01:28:59Z I apologize for not being clear in my edit. P1 is a minimizer of $||Q - P||$ and P2 is a minimizer of $||QBQ^{T} - PBP^{T}||$. I say &quot;a minimizer&quot; because there are multiple minimizers, but choosing a different representative does not necessarily make P1 behave as desired. http://mathoverflow.net/questions/81741/approximate-action-of-unitary-matrix-with-permutation-matrix Comment by Charles Bailey Charles Bailey 2011-11-23T20:36:11Z 2011-11-23T20:36:11Z I have included a counterexample in the edit to my question. Thanks for your help.