Questions tagged [dynamic-programming]
The dynamic-programming tag has no summary.
62 questions
0
votes
1
answer
295
views
How can we solve Hitting Set instance in time $O(2^k)$ using Dynamic programming, where $k$ is the number of sets?
Suppose we have a hitting set instance $(U, F)$ where $U$ is the universal set and $F$ is the family of subsets of $U$. $F$ has $k$ many sets $=\{f_1, f_2,...,f_k\}$ and $U$ has $n$ many elements. ...
- 21
1
vote
1
answer
365
views
Sources that prove solving 2-SAT with DP takes linear time
Would anyone have any sources that describe/an explanation of how solving 2-SAT using dynamic programming takes a linear amount of time? Can't seem to find a text that proves it in detail/formality. ...
- 11
0
votes
0
answers
220
views
Can one obtain an FPTAS for Knapsack by Rounding Weights (and not Profits)?
In the knapsack (KP) problem we are given a set $I = \{1,\ldots,n\}$ of items, each item $i \in [n]$ has a weight $w_i$ and a profit $p_i$. A classic Fully Polynomial time approximation scheme (FPTAS) ...
- 432
2
votes
0
answers
157
views
Can this relaxed subset-sum problem be solved with a smaller dynamic program? [closed]
Cross-post from CS.SE
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$.
...
- 2,334
9
votes
1
answer
312
views
Reference for automatically deriving dynamic programming algorithms from recursive algorithms?
This is what I'm looking for. Take a recursive algorithm:
def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n-1) + fib(n-2)
and turn it into ...
- 333
4
votes
0
answers
166
views
Split a string of positive numbers into substrings with decreasing totals
Suppose we're given a string of $n$ positive numbers and asked to split it into the maximum number of substrings whose totals are decreasing. I have an $O(n)$ time DP algorithm, but is it already ...
- 51
0
votes
0
answers
102
views
Dynamic programming algorithm to find a colorful subset of disjoint sets
Suppose there is a set $F=\{X_1 ,...,X_m\}$, such that $\forall 1\leq
i\leq m: |X_i|=3.$ Suppose we color the elements of $\bigcup F$ in
$3k$ colors. We wish to know if there is a subset $F'\...
user62160
6
votes
2
answers
350
views
The Dyck Language Correction Problem
Given a word $w$ over $\{ [, ] \}$, the alphabet of the two square brackets, the Dyck correction problem is to find the shortest sequence of edit operations that would make $w$ a Dyck word, i.e., a ...
- 541
1
vote
0
answers
53
views
Remove cycles from a stochastic comparison matrix, while doing the least amount of editing
Let $\mathcal P_n$ be the collection of all matrices $M \in [0, 1]^{n \times n}$ such that $M_{ij} + M_{ji} = 1$ for all $i, j \in [n]$. Such matrices are called comparison matrices. A comparison ...
- 291
3
votes
1
answer
490
views
Box stacking problem, and variants
You are given $n$ boxes and want to stack them to make a tallest possible tower, but you can only stack a box on top of another if the base is smaller in both dimensions. This is a classic dynamic ...
- 7,861
1
vote
1
answer
595
views
Is the knapsack variant with small profit and unlimited repetition of items NP-hard?
Consider the unbounded Knapsack problem where we are given $n$ items of integral weights $w_i$, integral profits $p_i$, and a max weight $W$. The goal is to maximize the total profit $\sum_i x_ip_i$ ...
- 29
0
votes
1
answer
157
views
Minimizing the gaps with incremental capacity
There are a single job, a machine and a set of $n$ slots. The machine has a capacity that increments by $\zeta(t)$ every slot $t=1,2,\ldots,n$. Initially (before the first slot), the machine has 0 ...
- 335
3
votes
0
answers
356
views
How to approach the "traveling salesman problem" with cost changing every time salesman reaches a new city
Let's say instead of finding the shortest path we have to maximize the profit in a year of the salesman under the following constraints.
Salesman can go to a different city only on weekends, all ...
- 131
2
votes
0
answers
244
views
Run Length eXtreme encoded length
In run length encoding (RLE) the code stream consists of pairs $(c_i,\ell_i)$, which is understood as writing the character $c_i$ repeatedly $\ell_i$ times.
Consider the following "improvement" of ...
- 183
2
votes
1
answer
136
views
Longest stack-sortable subsequence
Given an array of $n$ pairwise-different positive integers, the problem is to find the longest subsequence that is stack-sortable, i.e. avoiding the permutation pattern $231$.
How fast can this ...
- 193