Questions tagged [dynamic-programming]
The dynamic-programming tag has no usage guidance.
54
questions
46
votes
0answers
2k views
Monotone complexity of s-t connectivity
In the problem CONN, we obtain a directed $n$-vertex graph (encoded as a boolean string of $n^2$ bits, one for each potential edge), and want to decide
whether there is a path between all $n^2$ pairs $...
1
vote
0answers
36 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 ...
3
votes
1answer
108 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 ...
1
vote
1answer
224 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$ ...
0
votes
1answer
114 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 ...
6
votes
1answer
258 views
Counting words of length $n$ in an inherently ambiguous CFG?
There is a polynomial-time algorithm for computing the number of words of length $n$ in an unambiguous CFG $G = (V, \Sigma, R, S)$ (via a dynamic programming approach). However, for ambiguous CFGs, ...
2
votes
0answers
124 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 ...
2
votes
0answers
208 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 ...
2
votes
1answer
88 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 ...
0
votes
1answer
214 views
A dominate vector subset sum problem
Let $k$ be some constants (e.g. one can take $k=2$ for simplexity), for any $u,v\in \mathbb{R}$, we say $u$ dominate $v$ if $\forall 1\le i\le k,~ u[i]\ge v[i]$, write it as $u\succ v$.
Consider the ...
-4
votes
1answer
129 views
Ordering of sub problems in dynamic programming
1) Can every dynamic programming question be solved using 3 different orderings or can there be more than 3 or less than 3 ( like unique ordering )?
My understanding is that a) it might have a unique ...
1
vote
1answer
213 views
How can I rank paths through an HMM? [closed]
I have a profile hidden Markov model that I use to identify all instances of a user-defined pattern of symbols in a long sequence of symbols. I use the Viterbi algorithm to find the most probable path ...
-1
votes
1answer
311 views
Duration Viterbi Algorithm
I am searching for some good resources to understand the Duration Viterbi algorithm.
Does anyone knows a good resource to understand and learn how to model a Duration Viterbi Hidden Markov Chain ...
2
votes
0answers
54 views
Probabilistic linebreaking algorithm
I'm currently trying to implement this paper:
Bouckaert, Remco R., A probabilistic line breaking algorithm, Gedeon, Tamás D. (ed.) et al., AI 2003: Advances in Artificial Intelligence. 16th ...
31
votes
0answers
5k views
Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?
Roughly speaking, my question is:
How costly is to make a cyclic graph
acyclic while preserving all simple $s$-$t$ paths?
Let $K_n$ be a complete undirected graph on vertices $\{0,1,\ldots,n+1\}$.
(...
5
votes
3answers
457 views
Beating naive dynamic programming: examples similar to integer partitions?
Let $p(n)$ denote the number of partitions of $n\in\mathbb{N}$ (briefly, number of ways to split a pile of $n$ stones into $\geq1$ unordered nonempty parts). The classical dynamic programming ...
5
votes
0answers
73 views
Series-parallel extension of a partial order respecting a given total order
Consider a partial order $P$, a series-parallel order $Q$ and a total order $R$, such that $P \subseteq Q \subseteq R$. Given $P$ and $R$, we are asked to find $Q$ of minimum length.
An $O(n^3)$ ...
2
votes
0answers
105 views
Is scalable hardware support for LogCFL (= sAC^1) possible?
The (uniform) circuit classes $TC^0$, $NC^1$ and $sAC^1$ seem to lend themselves to efficient hardware implementation. But using an FPGA approach to create the circuits on the fly seems problematic, ...
1
vote
1answer
224 views
Max weight travel on a graph with deadline
Given a deadline $D>0$ and a complete graph $K_n$ (with loops) in which each edge $e_{ij}$ has a weight $w(e_{ij}) \ge 0$ and a travel time $l(e_{ij}) > 0$. Starting from one of the nodes, we ...
1
vote
0answers
50 views
Counting multiplicative closures
Given a set $S$, its multiplicative closure is the set
$$
\mathcal{M}(S) = \{s_1s_2\cdots s_k: k\in\mathbb{N},s_i\in S\}
$$
of products of zero or more elements of $S$. So the multiplicative closure ...
9
votes
0answers
500 views
How to prove “obvious” facts?
The title is somewhat "arrogant": say, most of us treat $P\neq NP$ as an "obvious" fact, albeit no proof is in sight. But my question is at a much, much lower level, is about a fact which "should be" ...
2
votes
0answers
172 views
Paper regarding the complexity of the longest path problem on weighted directed graphs of bounded treewidth
I would like to cite a paper/report/etc that solves the following problem polynomially in $n$:
Given a weighted directed graph $G=(V,E)$, $|V|=n$, of bounded treewidth $k \in \mathbb{N}$ and a source-...
10
votes
0answers
292 views
Monotone circuit complexity of matroids?
Call a monotone boolean function $f$ a matroid function if its minterms are bases of some matroid.
I am interested in monotone circuit complexity of such functions, even when we "tie hands" of these ...
16
votes
0answers
456 views
Can short-distance connectivity be harder than connectivity?
Has anybody seen the following (or similar) question being considered:
Can it be easier to determine the presence/absence of $s$-$t$ paths than to determine the
presence/absence of short $s$-$t$ ...
-1
votes
2answers
3k views
Dynamic Programming vs Greedy Algorithm
In (Sniedovich 2006) "Dijkstra's algorithm revisited: the dynamic programming connexion", Sniedovich provides us another interpretation of Dijkstra's algorithm as a dynamic programming implementation. ...
14
votes
1answer
959 views
Monotone arithmetic circuit complexity of elementary symmetric polynomials?
The $k$-th elementary symmetric polynomial $S_k^n(x_1,\ldots,x_n)$ is the sum of all $\binom{n}{k}$ products of $k$ distinct variables.
I am interested in the monotone arithmetic $(+,\times)$ circuit ...
15
votes
1answer
655 views
Is Dynamic Programming never weaker than Greedy?
In the circuit complexity, we have separations between powers of various circuit models.
In the proof complexity, we have separations between powers of various proof systems.
But in the algorithmic,...
11
votes
1answer
385 views
Covering string by palindromes
Given a string $w=\sigma_1\sigma_2\ldots\sigma_n$, a palindrome cover is a sequence $p_1p_2\cdots p_m$ of words $p_i$ such that $p_1p_2\cdots p_m = w$ and such that each $p_i$ is a palindrome.
How ...
1
vote
0answers
25 views
Which matrix of Q values is being used here?
This question refers to this paper: Using Free Energies to Represent Q-values in a Multiagent Reinforcement Learning Task
In section 2.1, equations (5) and (6), I am wondering which Q values are ...
4
votes
0answers
191 views
What is the current “state-of-the-art” solver for quadratic knapsack problems?
New to this forum, so please let me know if my question format is incorrect.
For linear KP with $n$ items and $c$ capacity, dynamic programming can find exact solutions in $\mathcal{O}(nc)$. I have ...
0
votes
0answers
1k views
How to solve such a graph optimization problem?
I have a graph optimization problem which is hard to describe in the title.
There is a component based system which consists of components and data transmissions between components(components and ...
11
votes
0answers
328 views
a geometric variant of k-medians. NP-hard or in P?
The following problem is a special case of k-medians. Is it NP-hard? Is it in P?
Input: $n$ points $(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n)$ with each $y_i \ge 0$, and an integer $k$.
Output: a set ...
5
votes
1answer
462 views
Long Cycle in Bounded Tree-Width Graphs using DFS and Dynamic Programming
For fixed parameter $k$, I would like to find a long cycle of length $\geq k$ in an undirected graph $G(V,E)$. This can be done in $O(k!2^k|V|)$-time [2] using 1) depth-first search (DFS) and 2) ...
3
votes
1answer
111 views
Locally sorted sequences
Let $S=s_1,\ldots,s_n$ be a sequence and $p$ be a permutation on the indices of $S$ such that $p$ sorts $S$.
Define a sequence to be locally sorted with degree $k$ if $\forall s_i \in S |p(i) - i | \...
1
vote
0answers
218 views
Dynamic Programming with two optimization goals
I am working on the problem of distributed database query planning. Existing work [1] uses dynamic programming to search the potential query plan space and find the one with minimal cost. However, I ...
-2
votes
1answer
909 views
Liner time complexity for wordwrap problem [closed]
Can some body explain me how to apply memoization technique to achieve linear time complexity for bellow.
http://www.geeksforgeeks.org/dynamic-programming-set-18-word-wrap/
5
votes
0answers
147 views
Evidence of non P-hard problems that require polynomial space?
It is admitted that a $\mathsf{P}$-complete problem requires polynomial space and thus cannot be efficiently parallelized. One purpose of these problems is that they can be used to 'defeat' an (...
0
votes
0answers
223 views
Calculating exact/approximate solution to a formula
Suppose we have a set of variable $\mathbf{y} = \left(y_1, ..., y_n \right)$. Also consider the set of functions $g_i(y_i), 1 \leq i \leq n$. Note that $g_i()$ is dependent only on $y_i$.
Consider ...
4
votes
1answer
80 views
Bellman principle and approximability
Does anybody know if a combinatorial optimzation problem that enjoys the Bellman's optimality principle can in automatic way be approximated?
4
votes
1answer
355 views
Problem understanding “connectivity” characteristic for the $k$-connected subgraph problem
I am reading this article, and I am having trouble to understand the 11th definition (page 7) about the connectivity characteristic. I do understand the raw ...
1
vote
4answers
210 views
Efficiently generate list of lightest intervals of a vector
Suppose a vector of size $n$ is given. The goal is to compute, $\forall i \in [n]$ the lightest interval of size $i$ (i.e. the interval whose sum is minimal).
For example, if we have the array:
<...
-6
votes
1answer
2k views
Dynamic programming and Divide and conquer approach [closed]
How does Dynamic Programming differ from Divide and conquer approach for solving problems?
Can anyone explain the essential idea of Dynamic Programming.
Thanks for any help.
2
votes
0answers
439 views
extension for Levenshtein distance
I am looking for an extension for Levenshtein distance (Edit distance) for multi dimensional strings (2D and 3D). I am not sure if there is a formal definition for multi dimensional or not, but here ...
6
votes
0answers
1k views
Euclidean TSP algorithms
Are there any known exact algorithms for Euclidean TSP that take advantage of the inherent structure of the problem? Do any of these algorithms have better asymptotics than $O(2^n n^2)$ of a DP ...
2
votes
1answer
145 views
Computing unique subset intersections
Given a set S = {si : {zj : z ∈ N} }, what is a time-efficient algorithm for computing the unique sets of intersections of all of the subsets of S?
As per @JeffE's comment below, there are edge ...
3
votes
2answers
283 views
Find two sequences of integers that have sum N but that don't have sub-sequences starting at the head of equal sum
This question arose from a discussion between a friend and I.
$A$ is a sequence of length $T$ where for any $a_i$ in $A$, $a_i \in \left\{{1, 2, 3}\right\}$
$B$ is a sequence of length $U$ where ...
2
votes
0answers
410 views
How can I find all numbers for which the XOR-sum is 0?
Given a list of integers $[a_1, a_2, \dots a_n]$, I want to find the number of $n$-tuples $(x_1,\dots,x_n)$ of integers such that the following three conditions are satisfied:
$x_1 \oplus x_2 \oplus \...
8
votes
2answers
982 views
Is there some mathematical closed form (or somewhat tight asymptotic one) for “Google Eggs Puzzle”?
The following brief description of the known "Google Eggs Puzzle" comes mainly from the web site Google Eggs:
Google Eggs Puzzle: Given n floors and m eggs, what is the approach to find the highest ...
7
votes
1answer
429 views
Does this bin packing problem have a name?
My problem is related to the standard bin packing problem (where you have bins of capacity $1$, items of capacity $(0,1]$, and want to pack the items into as few bins as possible), but there are a ...
0
votes
1answer
295 views
Variable profit knapsack [closed]
sorry for bad formatting earlier
We are given Cx,i, Cy,i, Cz,i ∈ ℕ and Px,i, Py,i, Pz,i > 0 for i=1,2,3 such that Px,1 < Px,2 < Px,3, Py,1 < Py,2 < Py,3, and Pz,1 < Pz,2 < Pz,3. We ...
