9
votes
Covering string by palindromes
This problem is called minimum palindromic factorization and this problem can be solved in $O(n \log n)$ time, see for example:
A subquadratic algorithm for minimum palindrome factorization by Fici ...
- 133
8
votes
Is Dynamic Programming never weaker than Greedy?
I think the answer to my Question 1 is affirmative: there are matroids on which simple DP fails badly! That is, simple DP may be much worse than Greedy when trying to solve an optimization problem ...
- 6,685
6
votes
Monotone arithmetic circuit complexity of elementary symmetric polynomials?
One challenge is that if you remove the "monotone" restriction, we do know how to compute such things efficiently. You can compute the value of all $S_0^n,\dots,S_n^n$ (evaluate all $n+1$ elementary ...
- 11.7k
4
votes
Reference for automatically deriving dynamic programming algorithms from recursive algorithms?
There's actually two questions here!
The transformation you ask about is called the tupling transformation. Basically, if your recursive calls follow a fixed pattern of overlap, a memo-table can be ...
- 32.4k
4
votes
The Dyck Language Correction Problem
The generalized problem, concerning Dyck($s$), for $s$ distinct pairs of parenthesis, was studied by Barna Saha in a paper entitled The Dyck Language Edit Distance Problem in Near-linear Time
B. Saha, ...
- 481
4
votes
Accepted
Longest stack-sortable subsequence
There's a polynomial-time dynamic programming algorithm in section 3.2 of https://ajc.maths.uq.edu.au/pdf/28/ajc_v28_p225.pdf (Albert et al, "Longest subsequences in permutations", Australas. J. ...
- 50.9k
3
votes
Sources that prove solving 2-SAT with DP takes linear time
It is a very basic exercise for undergraduate/graduate courses in Theoretical computer Science, and I think books avoid giving the solution so that students do not copy it without understanding. Here ...
- 2,733
3
votes
Is the knapsack variant with small profit and unlimited repetition of items NP-hard?
The problem (unbounded Knapsack with small profits) has a polynomial-time algorithm.
Theorem 1. For unbounded Knapsack with integer profits $(p_1,\ldots,p_n)$, there is an algorithm running in time ...
- 9,595
3
votes
Accepted
Minimizing the gaps with incremental capacity
Here's a poly-time dynamic-programming algorithm.
Lemma 1. The problem in the post has a poly-time dynamic-programming algorithm.
Proof sketch. Fix an input $(\zeta, c)$ over time slots $\{1,2,\ldots, ...
- 9,595
3
votes
Ordering of sub problems in dynamic programming
This is not a research level question. In any case DP is obtained by memoizing a recursion. If you start with an instance $I$ then the recursion generates several subproblems. You can obtain a ...
- 6,979
3
votes
The Dyck Language Correction Problem
If by "edit operations" you mean single character insertions, deletions, and substitutions then I believe a greedy algorithm works.
Let $x_i$ be the number of ] minus the number of [ in the ...
- 513
3
votes
Accepted
Dynamic Programming vs Greedy Algorithm
The main difference, in my view, is that DP solves subproblems optimally, then makes the optimal current decision given those sub-solutions. Greedy makes the "optimal" current decision given a local ...
- 7,595
2
votes
Beating naive dynamic programming: examples similar to integer partitions?
One nice example is the Hamiltonian Path problem is easily solvable in $O(2^n(n+m))$ time (Bellman, 1962) by dynamic programming over vertex subsets. In 2010 Björklund gave an algorithm running in ...
- 3,256
2
votes
Dynamic Programming vs Greedy Algorithm
Dynamic programming is not a greedy algorithm. It just embodies notions of recursive optimality (Bellman's quote in your question).
A DP solution to an optimization problem gives an optimal solution ...
- 121
2
votes
Counting words of length $n$ in an inherently ambiguous CFG?
It seems that this problem is NP-hard, if both the grammar and $n$ (in unary notation) are considered to be parts of the input.
There is a classical construction that is used to show that universality ...
- 245
2
votes
Dynamic programming and shortest path problem
Here's a less formal answer that I hope nonetheless addresses the spirit of the question.
Many standard dynamic-programming algorithms are easily seen to be equivalent to shortest-path (or longest-...
- 9,595
2
votes
Box stacking problem, and variants
If you model a box as a point $(b_1,b_2, \ldots, b_d)$, and you define the dominance relationship $p \prec q$ $\iff$ $p_i < q_i$, for all $i$, then you are looking for the longest chain in this ...
- 9,596
2
votes
A dominate vector subset sum problem
It's hard for $k\ge 2$ by a reduction from Partition. Let's first look at $k = 3$. Suppose that the input to Partition is the numbers $x_1, \ldots, x_n$, and their sum is $S$. For each $i$ create a ...
- 18.1k
1
vote
Max weight travel on a graph with deadline
Since you specifically ask later about the version of the problem in which the given path is restricted in how many times it visits each vertex/edge, I assume that the original version of the problem ...
- 2,758
Only top scored, non community-wiki answers of a minimum length are eligible