Questions tagged [dynamic-programming]
The dynamic-programming tag has no usage guidance.
26
questions with no upvoted or accepted answers
45
votes
0answers
1k 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 $...
30
votes
0answers
4k 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\}$.
(...
16
votes
0answers
447 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$ ...
11
votes
0answers
322 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 ...
10
votes
0answers
271 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 ...
9
votes
0answers
477 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" ...
7
votes
0answers
374 views
Embedded dynamic programming (and planar subgraph isomorphism)
In Planar Subgraph Isomorphism Revisited, Frederic Dorn obtains an improved algorithm for Planar Subgraph Isomorphism, by using a technique he calls Embedded Dynamic Programming. This technique ...
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 ...
5
votes
0answers
68 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)$ ...
5
votes
0answers
133 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, ...
5
votes
0answers
145 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 (...
4
votes
0answers
155 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 ...
2
votes
0answers
206 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
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 ...
2
votes
0answers
104 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, ...
2
votes
0answers
150 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-...
2
votes
0answers
385 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 ...
2
votes
0answers
397 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 \...
1
vote
0answers
74 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 ...
1
vote
0answers
49 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 ...
1
vote
0answers
24 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 ...
1
vote
0answers
216 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 ...
1
vote
0answers
476 views
Converting a bounded knapsack problem to 0/1 knapsack problem
I originally posted this question at the programmers section of StackExchange (because that section is supposed to deal with data structures and algorithms), but they suggested posting in the math ...
0
votes
0answers
46 views
choosing the best subset where the metric is based on pairwise relationship
I want to model the competition between agents.
Say there is a set of agents, and at each time step each agent $i \in \{0,1,\cdots, n-1\}$ can select a nonnegative number $x_i$ from a given range $[0,...
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 ...
0
votes
0answers
193 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 ...
