# Questions tagged [dynamic-programming]

The tag has no usage guidance.

51 questions
Filter by
Sorted by
Tagged with
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 ...
46 views

216 views

### Dynamic Programming with two optimization goals

I am working on the problem of distributed database query planning. Existing work  uses dynamic programming to search the potential query plan space and find the one with minimal cost. However, I ...
829 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 (...
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 ...
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.
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 ...
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 ...
420 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  using 1) depth-first search (DFS) and 2) ...
354 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 ...
397 views

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