snippetMinor
How to reduce to an NP-hard problem?
Viewed 0 times
problemreducehardhow
Problem
For an assignment I have to program an application to schedule conversations.
There is an event where representatives of the elementary schools talks with the representatives of high schools. They will talk about the students that will be transferred to the highschool. There are approximately 200 elementary schools and 40 high schools that will be participating in this event. The schools already know which student is transferring to which high school. The conversations will only be between representatives of E and H from student that will be transferring to H.
The rules are:
students per representatives.Each conversation last 5 minutes per student. If a group consist of 1 student, this conversation last 10 minutes.
representatives will only face the same representative once.
waiting time is an empty timeslot between the 1st and last
conversation.
The problem is that I know that this is hard to solve, but I dont know if it's NP-hard. Right now I only know this problem is similar to a Job Shop Problem. What can I do to proof that my problem is NP-hard? I read that I need to reduce a known problem to my problem. But how do I do this? I have read different articles and books, but I still don't understand the steps to do it.
There is an event where representatives of the elementary schools talks with the representatives of high schools. They will talk about the students that will be transferred to the highschool. There are approximately 200 elementary schools and 40 high schools that will be participating in this event. The schools already know which student is transferring to which high school. The conversations will only be between representatives of E and H from student that will be transferring to H.
The rules are:
- The duration of each conversation is based on the amount of
students per representatives.Each conversation last 5 minutes per student. If a group consist of 1 student, this conversation last 10 minutes.
- No timeclashes
- All the students of the same group will be scheduled together, so, a
representatives will only face the same representative once.
- Timespan is 13.00-19.00
- The waiting time of a representative is at most 20% of his time. A
waiting time is an empty timeslot between the 1st and last
conversation.
- Schedules for 2 days
- Each representatives participate for 1 day.
The problem is that I know that this is hard to solve, but I dont know if it's NP-hard. Right now I only know this problem is similar to a Job Shop Problem. What can I do to proof that my problem is NP-hard? I read that I need to reduce a known problem to my problem. But how do I do this? I have read different articles and books, but I still don't understand the steps to do it.
Solution
Just an extended comment.
I think that before trying to find a reduction, you should try to better formalize the problem:
For example:
-
If a group consist of 1 student, this conversation last 10 minutes. $\rightarrow$ it is equivalent to a group of two students, so you can remove it;
-
Timespan is 13.00-19.00 $\rightarrow$ in the other rules you use minutes, so convert the "timespan" to $T$ minutes;
-
try to think if a simplified version of the problem has a quick solution or it can be still hard (e.g. if the event last only one day rules 7 and 8 can be dropped)
-
express the rules with a math formula: e.g "if an elementary group $E$ of $n$ students talk with a high school group $H$ of $m$ students then the total time $TT$ required is $TT(E,H)=....$"; "the total max wait time $WT$ for group $E$ is $WT = ...$"
Furthermore there is a point that it is not clear (to me):
I think that before trying to find a reduction, you should try to better formalize the problem:
- define exactly what the parameters of the problem are, formalize their constraints, and formalize the question;
- try to simplify (or remove) the details;
For example:
-
If a group consist of 1 student, this conversation last 10 minutes. $\rightarrow$ it is equivalent to a group of two students, so you can remove it;
-
Timespan is 13.00-19.00 $\rightarrow$ in the other rules you use minutes, so convert the "timespan" to $T$ minutes;
-
try to think if a simplified version of the problem has a quick solution or it can be still hard (e.g. if the event last only one day rules 7 and 8 can be dropped)
-
express the rules with a math formula: e.g "if an elementary group $E$ of $n$ students talk with a high school group $H$ of $m$ students then the total time $TT$ required is $TT(E,H)=....$"; "the total max wait time $WT$ for group $E$ is $WT = ...$"
Furthermore there is a point that it is not clear (to me):
- suppose you have an elementary school group $E$ having $n$ students that talk with a high school group $H$ having $m$ students; what is the total time required? (1) $5 n$ (the talk is public) or (2) $5 ( n / m)$ (each student of E talks with a single student of H). If the talk is public, then the number of students is redundant, and you can think only in terms of total time required by a school group.
Context
StackExchange Computer Science Q#3439, answer score: 5
Revisions (0)
No revisions yet.