Dynamic programming is a mathematical optimization/programming approach applicable if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. A classic example is the Towers of Hanoi.

learn more… | top users | synonyms

-1
votes
1answer
42 views

Is this function bounded or not?

$f(x) = \left(1-\frac ax\right)^2$ where both $x>0$, $a>0$ Is this function bounded? i.e. is there an M such that $f(x) ≤ M < \infty$ ? How can I figure this out? Thanks very much in ...
0
votes
0answers
14 views

Geers MPC metric - understanding magnitude error and phase error

It is regarding this question/subject Integrate two sets of Data and check similarity I'm applying the formulas mentioned [here]. But I still can't understand these error rates M and P. It is ...
0
votes
0answers
26 views

Dynamic Optimization - Transversality Condition for Infinite Horizon Case

When solving dynamic optimization problem such as $$ \max \int_0^\infty f(t,x,x')dt $$ $$ \ s.t. x(t_0)=x_0 $$ we can use the Euler equation to obtain a differential equation to solve. ...
0
votes
1answer
25 views

Is this algorithm for 3D spherical interpolation correct?

I am attempting to write a spherical interpolation algorithm for for the application of smooth 3D animation in a game. The scripting language that the game engine uses is Lua. It is often easier for ...
6
votes
0answers
43 views

Approximate Dynamic Programing - Discount Factor for Very Long Horizons

I want an optimal strategy for a very long time horizon, say $K=100000$. I have dynamic decision making problem where next state $x_{k+1}$ is determined by the probability distribution ...
0
votes
0answers
8 views

Dynamic Programming - Change in Control Variables

I have a question on DP. The problem is $V(x_t,y_t) = max\{u(k_t) + \gamma \log(x_t) + \beta V(x_{t+1}, y_{t+1})\}$ Subject to $k_t +y_{t+1} + p_{t+1}x_{t+1} = w_t + (1+r)y_t + p_t x_t$ and $c_t, ...
2
votes
1answer
25 views

Sequential information discovery in minimum number of steps when some items have information about other items

There are N items, say three: call them A B and C. For each item, there is an associated bit (0 or 1) and there is a prior probability that the bit is 1, call them p(A), p(B) and p(C). There is some ...
1
vote
1answer
36 views

How to come up with this recurrence relation for putting p rooks in a m×n chessboard?

I have a m×n chessboard and I have to put p rooks in the board so that no two of them are in attacking position. (Two rooks attack each other if they are in the same row or same column) How many ways ...
1
vote
1answer
34 views

Probabilistic dynamic programming question

A gambler has 2 dollars. He is allowed to play a game four times and his goal is to maximize his probability of ending with at least 6 dollars . If the gambler bets $b$ dollars then with ...
3
votes
1answer
37 views

Dynamic programming recursion

In a book by Wayne Winston for operations research I found this question. Here's how I did it: Let $t$ be the no.of subjects to pass and let h be the no.of hours she has in hand for studying. ...
4
votes
1answer
163 views

Cover the grid graph with simple cycles

I have a two dimensional n x m grid graph. And I want to find in how many ways this grid can be covered with simple cycles (it can be a one cycle or it can be many ...
0
votes
0answers
11 views

How to do linear quadratic dynamic programming with non homogeneous quadratic equation

I am not well versed on matrix algebra and linear quadratic programming. I am wondering if it is possible to make a non-homogeneous equation into a homogeneous one. I need to make the following ...
1
vote
1answer
48 views

Special Palindromic String

A string of length $N$ can be made from $6$ characters $a$, $b$, $c$, $d$, $e$ and $f$. There are some rules to make such a string: 1) $b$ can not come directly after $a$. 2) $d$ can not come ...
1
vote
1answer
30 views

An Algorithmic approach to the secretary problem with unknown n

I've been reading about the secretary problem these days and I got the idea for the case when we know the number of applicants $n$ in advance. I'd like to know what would be an algorithmic approach ...
0
votes
0answers
10 views

Bounded Knapsackproblem Formula DP

I knew how the binary Knapsack works with Dynamic Programming. But, now I am interested. How does the recursive formula look like if I allow n€{0,1,2} of the same item to be in the Knapsack? The only ...
0
votes
2answers
96 views

A mathematical brain teaser in probability field

That is a brain teaser but it is also a mathematical problem in probability field. One day, a man have been trapped into a building which has 18 floors. Now, he want to leave the building but there ...
0
votes
1answer
20 views

Solving for max () in Viterbi algorithm

In simple terms, what is the proper way to solve for max. I am working with the Viterbi algorithm and am now stuck on how to solve this part of the equation. pc(G,2) = 0.3 + ...
1
vote
0answers
34 views

Determining the optimal cost through dynamic programming.

There are $n$ houses numbered $\{1, 2, 3, \dots, n\}$. The cost of laying a cable that serves houses $j, j+1, j+2, \dots, j+k $ is $f (j, k)$. One cable can serve a maximum of 10 houses. The ...
1
vote
1answer
22 views

A clarification regarding dynamic programming.

This is a question regarding dynamic programming. The document to which I am referring is this (pg 325). It says that $$v_n(s_n)=\text{Min}\{t_n(s_n)+v_{n-1}(s_{n-1})\}$$ Here $v_n(s_n)$ is the ...
0
votes
0answers
40 views

how can we explain that the all slack point is feasible

how can we explain that the all slack point is feasible when solving a linear programming problem using the simplex method Thanks in advance, i appreciate all the help.
0
votes
0answers
29 views

Can someone help me to get the mathematical formula for below scenario?

There was a question in topcoder, and its given below.I had a glance at the source code,but i didn't understand anything. Can someone help me to get the mathematical background or formula behind this ...
0
votes
1answer
69 views

The Change-making problem algorithm proof (at the dynamic programming method)

I saw here the algorithm for the "Change-making problem" (at the dynamic programming method). I saw it here: http://www.columbia.edu/~cs2035/courses/csor4231.F07/dynamic.pdf I'm trying to find a ...
1
vote
0answers
46 views

kalman filter matrices

I would like to apply a kalman filter on data I receive from a sensor, i.e. a lightsensor. I have 3 light sensors, 1 for each axis. I am grouping all the data from the three sensors in 1 formula. My ...
2
votes
1answer
54 views

Is this the correct minimum number of coins needed to make change?

The Problem: On Venus, the Venusians use coins of these values [1, 6, 10, 19]. Use an algorithm to compute the minimum number of coins needed to make change for 42 on Venus. State which coins are used ...
1
vote
1answer
34 views

Where does 13 come from?

I am going over the Rod Cutting Problem Everything makes sense to me until For example, $L$ = {9} has the total cost Cost($L$) = $P$[9] = 13, whereas $L$' = {1,1,1,1,1,1,1,1,1} has the total cost ...
0
votes
0answers
19 views

I have a binary plot in some coordinate space, how do I find slope most efficiently?

So basically I have a 2d array filled with 1s and 0s. There should be a linear slope associated with the 1s, and I need to find that linear slope with the best accuracy and quickness possible. How ...
0
votes
0answers
33 views

How to solve problem using dynamic programming

How to solve this problem using dynamic programming: The company produces five types of electronic games (E1, E2,..., E5) and five types of mechanical toys (M1, M2,..., M5). On the market ...
0
votes
0answers
42 views

How do I compute the expected value of a function of two correlated random variables?

I'm trying to figure out how to properly compute the expected value of a function of two random variables and constants. The two random variables determine the state transitions in an MDP: The states ...
1
vote
0answers
24 views

Optimal Stopping Problem (With looking backwards)

Say you are trying to sell a good at the highest price. You draw independently from $F(p)$. The history of observations is $P = \{p_1, p_2,\dots\}$. Observing the $i$th price costs $c_i$, where the ...
5
votes
1answer
100 views

Two pawns walking in a complete graph

We have a complete graph $G = \langle V,E\rangle$ with non-negative values on edges. Let $C = \{v_1,v_2,\ldots,v_n\}$ be an ordered collection of $G$'s vertices. At the beginning we have two pawns in ...
1
vote
0answers
18 views

Is there any general algorithm to solve such a 3D cutting problem?

Suppose a cuboid $\mathbb{A}$ has $L$,$M$ and $N$ as its length, width and height respectively, where $L\ge{M}\ge{N}>0$; Now we want to cut $\mathbb{A}$ into smaller cuboids with length $x$, width ...
0
votes
0answers
18 views

Spin-off of Scheduling Weighted Interval Problem

I'm trying to solve a problem in which, given a + sign shaped area of land (with no width) and a list of contiguous sections of the land (segments, T-shapes, smaller + shapes, etc), each with an ...
0
votes
2answers
58 views

Find Algorithm, given a list of arcs, that maximizes number that fit on a circle

I'm trying to find an optimal algorithm that, given a list of arcs $(x_i, y_i)$, where $x_i$ and $y_i$ are the starting and ending angle measurements of the arc in radians, maximizes the number of ...
2
votes
1answer
80 views

How to do continuous-time Bayesian updating?

I am reading a game theory lecture notes. Some parts involve a continuous time Bayesian updating computation which I didn't really understand. There are two states $\{Good,Bad\}$. At time t people ...
1
vote
3answers
85 views

Finding the formula for summation of the series

I was just solving a competitive programming question, wherein I found out that a formula can be used for solving it efficiently. Problem statement: http://www.spoj.com/problems/TOHU/ I tried a lot to ...
0
votes
0answers
20 views

Approach for this Popular Algorithmic Problem

Given a matrix we have to select one value from each row so that the total value cost selected is minimum. Now the problem is we cannot select column "0" to "J" in "I"th row if we have selected ...
4
votes
1answer
85 views

Integrate two sets of Data and check similarity

I have the following CSV Data I used Excel Charts to plot the Data I want to compare these Data with other Data, in another word i want to comapre 2 curves and check the similarity between them in ...
0
votes
2answers
70 views

Minimize a non-convex function subject to linear dynamics constraint

I want to solve the following problem: $$\min\limits_{\bf u} \frac{\bf c^T {\bf x} (T_f)}{\| \bf c\|\|{\bf x} (T_f)\|}$$ subject to $$\dot{\bf x} (t) = A {\bf x}(t) + B {\bf u}(t)$$ $$x(0) = x_0$$ ...
2
votes
1answer
26 views

Explanation of strategies in infinite horizon dynamic programming problem

My question is regarding the Bellman equation regarding strategy $\sigma^{(1)}$ on the last 2 lines (I have attached pictures of the book below). If we know that all future states will have value of ...
1
vote
0answers
16 views

Scheduling problem

Consider the following setting: $N$ jobs, each has a starting time, which is assumed to be a natural number and all N numbers are distinct, e.g., the 1st job has starting time at 5, the 2nd is 6, the ...
0
votes
0answers
23 views

Pyramidal TSP without weight

Say $G=(V,E)$ with $V=\{1,...n\}$ and $l(i,j)$ is the distance of arc $(i,j) \in E$. The aim is to find a pyramidal path in $V$ with minimal length. A pyramidal path is a sequence of vertices $(n,i_1, ...
0
votes
1answer
41 views

Greedy choice property

There are two versions of the Knapsack problem, the integer and the fractional one. The difference between the integer and the fractional version of the Knapsack problem is the following: At the ...
0
votes
1answer
134 views

Maximize profit with dynamic programming

I have 3 tables… $$\begin{array}{rrr} \text{quantity} & \text{expense} & \text{profit}\\ \hline 0 & 0 & 0 \\ 1 & 100 & 200 \\ 2 & 200 & 450 \\ 3 & 300 & 700 ...
-5
votes
1answer
225 views

Are the propositions right?

I want to choose if the following propositions are true or false and justify the reason for the choice. Polynomial: good, exponential: bad. Radix Sort works correctly if we use any right sorting ...
1
vote
1answer
82 views

Count connected components after $M$ marbles removed

There are $N$ marbles in a line, numbered $1$ through $N$ from left to right. We need to count numbers of ways to remove exactly $M$ marbles such that there are exactly $C$ remaining connected ...
0
votes
2answers
59 views

Setting up the Bellman equations for dynamic programming

I have the following question I want to understand. The owner of a chain of three grocery stores has purchased five crates of fresh strawberries. The estimated probability distribution of ...
2
votes
1answer
116 views

Why does the Hamilton Jacobi Bellman Equation imply Pontryagin's Minimum Principle

I'm having difficulty understanding the proof that allows us to go from the Hamilton-Jacobi-Bellman equation to to the Pontryagin Min(Max) Principle. Lets consider $x(t)$ and $u(t)$ as real valued ...
2
votes
0answers
30 views

Reducing a Knapsack-type problem to a known problem

The Quadratic Knapsack problem, introduced by Gallo, is an optimization problem in the following form: $max \sum_{i=1}^n{\sum_{j=1}^n{q_{ij}x_ix_j}}$ $s.t \sum_{i=1}^n{w_ix_i} \leq c$ $x \in \{0, ...
0
votes
1answer
31 views

Optimal schedule for a set of jobs

Assume that yo have a set of jobs in which each has only a processing time that you need to minimize the sum of the completion (finish) times. Prove that your schedule is optimal. The wording throws ...
0
votes
1answer
112 views

Cost function with stochastic variable

I'm not as well versed as I would like to be to confidently evaluate the following cost function. So any affirmation would be appreciated. Given an initial stage $x_0$ $$J_\pi(x_0) = \lim_{N \to ...