Unanswered Questions
361 questions with no upvoted or accepted answers
12
votes
0
answers
236
views
Can you multiply complex 2x2 matrices in fewer than 21 real multiplies?
It is well known that 2x2 matrices can be multiplied using just 7 (instead of the obvious 8) multiplications in the ground field (Strassen-Winograd, etc.). It is also well known that complex numbers ...
- 201
12
votes
1
answer
5k
views
Finding the longest repeating subsequence
Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ ...
- 280k
9
votes
0
answers
784
views
How can the shortest traveling salesman tour be found in $O(2^n poly(n))$ time and less than exponential space?
I'm stuck on problem 9.4 from The Nature of Computation which reads:
Dynamic Salesman. A naive search algorithm for TSP takes $O(n!)$ time to check all tours. Use dynamic programming to reduce this ...
- 1,058
8
votes
0
answers
647
views
Chained operations on sequences with two operators
Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation?
Can we learn from matrix chain multiplication? A generalization of matrix chain ...
CommunityBot
- 1
6
votes
0
answers
97
views
Scheduling tasks on a graph with assistance
This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following:
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
CommunityBot
- 1
6
votes
1
answer
124
views
A dynamic program to decide whether the solution is in a given range
In the subset sum problem, the input is a list of positive integers $x_1,\ldots,x_n$ and an integer $T$, and the goal is to decide whether there is a subset of sum exactly $T$.
The problem can be ...
- 6,188
5
votes
0
answers
457
views
Count Wildcard Parenthesizations of a String
Let $\Sigma = \{ (, ), ? \}$ be an alphabet. For a given string $s \in \Sigma^*$, we denote by $f(s)$ the number of ways to replace each symbol $?$ either with $($ or with $)$ such that $s$ is ...
- 73.1k
5
votes
0
answers
180
views
Sequence Alignment with Skips
In my thesis I am working on a problem connected with sequence alignment, in particular, I deal with the Dynamic Time Warping (DTW) algorithm (see this for more), which is used to evaluate the ...
5
votes
0
answers
190
views
A matrix rank problem over finite fields
I have already asked a similar question here, but since I have not got an acceptable answer, I decided to ask a simpler version of the question here.
Let $M|\mathbf w$, where $M$ is a matrix and $\...
CommunityBot
- 1
5
votes
1
answer
1k
views
2D version of LeetCode house robber problem
The house robber problem of leetcode can be described as followed :
A robber enters a colony of houses numbered from 1 to n. Every house has a number printed on the top of it. That number is the ...
CommunityBot
- 1
4
votes
0
answers
247
views
Low-rank matrix completion is NP-hard
In looking into the problem of low-rank matrix completion / relaxations of the general problem to derive exact solutions, many papers cite that the original formulation is NP-hard but I cannot find a ...
4
votes
0
answers
157
views
Find a dynamic programming solution that minimize the sum of the diameters of two clusters?
I asked a question at this link, where I suggested a greedy algorithm for this problem:
Suppose given $2n$ points in the plane and we want partition points into two clusters $C_1$ , $C_2$ such that ...
- 83
4
votes
0
answers
69
views
minimizing a pairwise sum with respect to a sequence of integers
Let $m$ and $n$ be two integers, where $m \leq n$.
Suppose you are given $m^2$ matrices $W^{i,j} \in \mathbb{R}^{n \times n}$ for $i, j \in \{1, \dots, m\}$.
The goal is to find a sequence $a$ of $m$ ...
- 515
4
votes
0
answers
227
views
Assign n people to m rooms of different sizes, such that noone is alone
I'm looking for an efficient way to assign n people to m rooms in a very specific way.
INPUT:
The program receives two sets of people (set of males and set of females), as well as a set of available ...
D.W.♦
- 167k
4
votes
0
answers
290
views
Maximum weight independent set in a King's graph
I would like to find a maximum weight independent set in a finite section of a King's graph.
For an $m\times n$ King's graph where $n \ll m$, we can use an $O(2^{2n} m)$ bitmask dynamic programming ...
- 141