User charles bailey - MathOverflow

#P version of SUBSET SUM

2012-04-24T02:22:29Z

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.

The corresponding #P problem asks HOW MANY subsets of $S$ sum to zero.

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.

Thanks, Charles

Shortest absolute value of path in graph

2012-03-11T19:45:14Z

Suppose we have a weighted, acyclic digraph, with positive and negative edge weights.

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?

Thanks, Charles

Approximate action of unitary matrix with permutation matrix

2011-11-23T19:13:47Z

Given a unitary matrix Q and a symmetric matrix B, I am trying to find a permutation matrix P such that

$ || QBQ^{T} - PBP^{T} ||_{F} $

is minimized.

The straightforward method of minimizing $ || Q - P ||_{F} $ does not work.

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.

Does anyone have any suggestions?

Thanks,

Charles

Edit:

An example that shows that minimizing $||Q-P||_{F}$ does not work is as follows:

B = \begin{array}{cc} 0 & 1 & 1 & 1 \newline 1 & 0 & 0 & 0 \newline 1 & 0 & 0 & 0 \newline 1 & 0 & 0 & 0 \newline \end{array}

Q =
\begin{array}{rr} -0.6544 & -0.6544 & 0.1585 & 0.3440 \newline -0.0473 & -0.0473 & -0.9624 & 0.2633 \newline -0.6864 & 0.3136 & -0.1561 & -0.6373 \newline 0.3136 & -0.6864 & -0.1561 & -0.6373 \newline \end{array}

$P_{1}$ = \begin{array}{rr} 0 & 0 & 1& 0 \newline 0 & 0 & 0 & 1 \newline 0 & 1 & 0 & 0 \newline 1 & 0 & 0 & 0 \newline \end{array}

$P_{2}$ = \begin{array}{rr} 1& 0& 0 & 0\newline 0 & 0 & 1 & 0\newline 0 & 1 & 0 & 0\newline 0 & 0 & 0 & 1\newline \end{array}

With these matrices,

\begin{align} || Q - P_{1} || &< || Q - P_{2} || \end{align}

but \begin{align} || QBQ^{T} - P_{1}BP_{1}^{T} || &> || QBQ^{T} - P_{2}BP_{1}^{T} || \end{align}

Comment by Charles Bailey

2012-04-24T19:05:09Z

By size of the element, I mean their absolute values. - Charles

Comment by Charles Bailey

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

Comment by Charles Bailey

2012-03-11T20:23:43Z

The weights are integers in the interval [-c,c] for some integer constant c.

Comment by Charles Bailey

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 "a minimizer" because there are multiple minimizers, but choosing a different representative does not necessarily make P1 behave as desired.

Comment by Charles Bailey

2011-11-23T20:36:11Z

I have included a counterexample in the edit to my question. Thanks for your help.