## 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

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?

Hi,

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

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?

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?

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?

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