The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Questions tagged [dynamic-programming]

The tag has no usage guidance.

50 questions
Filter by
Sorted by
Tagged with
46 views

215 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 ...
813 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/
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 (...
190 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 ...
79 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?
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: <...
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.
376 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 ...
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 ...
417 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) ...
353 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 ...
144 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 ...
282 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 ...
396 views

410 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 ...
455 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 ...
2k views

### Dynamic programming and shortest path problem

Several months back, I asked in math.SE the following question I wonder if any dynamic programming problem can always be converted to a source-sink shortest path problem in a network with source ...
397 views

### Cannot understand the problem of Bitonic Euclidean Traveling-Salesman [closed]

I am referring to the problem in Introduction to Algorithms. I kind of fail to understand the problem. From what I see, I need to sort the x-coordinates of the given set of points and then form a ...
373 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 ...