Skip to main content
MathOverflow

Return to Question

added 10 characters in body
Source Link
Turbo
Turbo
  • 13.9k
  • 1
  • 27
  • 76

  1. Given a permutation matrix the'the question is to decide if thethere is a permutation matrix isrepresenting a cycle matrix within Hamming distance $d$ from given matrixmatrix'. Is there an efficient algorithm for it?

  2. Given a permutation matrix the question is there always a permutation matrix which is a cycle matrix within Hamming distance $O(1)$ from given matrix? If not what is the worst case Hamming distance?

  3. Given a permutation matrix the question is there always a permutation matrix which is a cycle matrix within Euclidean distance $O(1)$ per row and per column from given matrix? If not what is the worst case Euclidean distance $O(1)$ per row and per column?

  1. Given a permutation matrix the question is if the permutation matrix is a cycle matrix within Hamming distance $d$ from given matrix. Is there an efficient algorithm for it?

  2. Given a permutation matrix the question is there always a permutation matrix which is a cycle matrix within Hamming distance $O(1)$ from given matrix? If not what is the worst case Hamming distance?

  3. Given a permutation matrix the question is there always a permutation matrix which is a cycle matrix within Euclidean distance $O(1)$ per row and per column from given matrix? If not what is the worst case Euclidean distance $O(1)$ per row and per column?

  1. Given a permutation matrix 'the question is to decide if there is a permutation matrix representing a cycle within Hamming distance $d$ from given matrix'. Is there an efficient algorithm for it?

  2. Given a permutation matrix the question is there always a permutation matrix which is a cycle matrix within Hamming distance $O(1)$ from given matrix? If not what is the worst case Hamming distance?

  3. Given a permutation matrix the question is there always a permutation matrix which is a cycle matrix within Euclidean distance $O(1)$ per row and per column from given matrix? If not what is the worst case Euclidean distance $O(1)$ per row and per column?

added 202 characters in body
Source Link
Turbo
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Hamming distance globally and Euclidean distance locally to a cycle

Given a permutation matrix the question is if the permutation matrix is a cycle matrix within Hamming distance $d$ from given matrix. Is there an efficient algorithm for it?

  1. Given a permutation matrix the question is if the permutation matrix is a cycle matrix within Hamming distance $d$ from given matrix. Is there an efficient algorithm for it?

  2. Given a permutation matrix the question is there always a permutation matrix which is a cycle matrix within Hamming distance $O(1)$ from given matrix? If not what is the worst case Hamming distance?

  3. Given a permutation matrix the question is there always a permutation matrix which is a cycle matrix within Euclidean distance $O(1)$ per row and per column from given matrix? If not what is the worst case Euclidean distance $O(1)$ per row and per column?

Hamming distance to a cycle

Given a permutation matrix the question is if the permutation matrix is a cycle matrix within Hamming distance $d$ from given matrix. Is there an efficient algorithm for it?

Hamming distance globally and Euclidean distance locally to a cycle

  1. Given a permutation matrix the question is if the permutation matrix is a cycle matrix within Hamming distance $d$ from given matrix. Is there an efficient algorithm for it?

  2. Given a permutation matrix the question is there always a permutation matrix which is a cycle matrix within Hamming distance $O(1)$ from given matrix? If not what is the worst case Hamming distance?

  3. Given a permutation matrix the question is there always a permutation matrix which is a cycle matrix within Euclidean distance $O(1)$ per row and per column from given matrix? If not what is the worst case Euclidean distance $O(1)$ per row and per column?

Source Link
Turbo
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Hamming distance to a cycle

Given a permutation matrix the question is if the permutation matrix is a cycle matrix within Hamming distance $d$ from given matrix. Is there an efficient algorithm for it?