What is the name of this kind of DP problems?

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

Post Reply
DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

What is the name of this kind of DP problems?

Post by DJWS » Fri Jun 13, 2008 6:41 am

Hi,

I found some similar dynamic programming problems: 714, 907, 662.
Is there a formal name for this kind of problems?

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: What is the name of this kind of DP problems?

Post by sohel » Fri Jun 13, 2008 7:40 am

Matrix Chain Multiplication :: more commonly known as MCM.

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Re: What is the name of this kind of DP problems?

Post by DJWS » Fri Jun 13, 2008 11:12 am

I think MCM is 348 or 442 instead.

In 714, 907, and 662, we make k partitions of a given sequence and minimize the maximal partition.
We can use DP, optimized DP, or binary search to solve this kind of problems.
That is special. Thus I wonder if a formal and unique name exists.

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Re: What is the name of this kind of DP problems?

Post by DJWS » Sat Jun 14, 2008 4:52 am

Finally I found 662 is called 'p-median problem' after googling around 3 hours. It belongs to the 'location-allocation problem.'

The p-median problem is a well-known NP problem (but not for me :wink: ). There are many approaches to solve it, for example, integer programming. There are also many variants of this problem like the p-center problem, the uncapacitated facility location problem, and the range assignment problem.

Here is a reference: http://ramanujan.math.trinity.edu/tumat ... port96.pdf

Post Reply

Return to “Other words”