Re: [boost] GSoC 2013 : Implementing Dynamic Programming Algorithms

Subject: Re: [boost] GSoC 2013 : Implementing Dynamic Programming Algorithms
From: Aman Gupta (amangupta052_at_[hidden])
Date: 2013-04-09 18:35:11

Hi,

Thanks for the reply. The first thing I want to implement is a
Integer-Knapsack problem which takes in a precision error(i.e. an epsilon
which is a indicator of the allowed error in the input)
The input parameters are Weights, Values and the error. The first thing to
do is massage the values according to the error (e.g. if the value is ~10^4
divide it down to ~10^3 according to the error)  then run the a dynamic
programming algorithm, which has a running time of O(n^3/e) (n : number of
items, e :error) Hence, an arbitrarily close approximation is possible with
a running time trade-off.

Also, a vanilla variety of the knapsack problems(with small instances)
which gives the optimal solution can also be implemented.

I also want to implement the assignment problem, which also arises in a lot
of situations in real life ( http://en.wikipedia.org/wiki/Assignment_problem)
using the Hungarian Algorithm.

I realize this requires effort but I'm really interested in adding a
feature to the boost library.

Regards,
Aman Gupta