# Tag Info

### 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 ...

### 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 ...

### 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 ...

### 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 ...

### 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, ...
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. ...

### 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 ...

### 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 ...