For an assignment i need to program an application to schedule conversations. Something similar to speeddating or Pta meeting. The problem is that i know that this is hard to solve, but i dont know if its np-hard. What can I do to proof that this problem is np-hard? I read that i need to reduce a known problem to my problem. But how do I do this?

There is an event where Respresentatives of the elementary schools talks with the representatives of a highschool. They will talk about the students that will be transferred to the highschool. There are approximately 200 elementary schools and 40 highschools that will be participating in this event. And this event last 2 days.

The rules are:

  1. The duration of each conversation is based on the ammount of students per representatives. Each conversation last 5 minutes per student. If a group consist of 1 student, this conversation last 10 minutes.
  2. No timeclashes
  3. All the students of the same group will be scheduled together, so, a representatives will only face the same representative once.
  4. Timespan is 13.00-19.00
  5. 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.
  6. Schedules for 2 days
  7. Each representatives participate for 1 day.

Based on this i will decide if i will use a heuristic algorithm to solve this problem.

Sorry for my english

Thanks in advance

  • $\begingroup$ Hi Nico Liu. Welcome to Scicomp! Can you describe the problem in more detail? This will help us to determine if a reduction can be made and/or how to do it. $\endgroup$ – Paul Aug 29 '12 at 1:45
  • $\begingroup$ I have edited my question $\endgroup$ – Nico Liu Aug 29 '12 at 6:30
  • $\begingroup$ I believe your question fits better into computER (not computATIONAL!) science (cs.stackexchange.com). IMHO this forum should be named "Scientific computation". $\endgroup$ – Igor F. Sep 3 '12 at 15:02

Showing that one problem can be reduced to another to demonstrate that it is NP-hard is in general not a trivial matter. It means that you have to show that you can reformulate the problem as another one for which it is known that it is NP-hard and then obtain the solution of the original problem from the solution of the reformulated problem.

The more common way is to see if someone has already looked at your particular problem. What you have here is a typical resource allocation problem. Consider, for example, your high school reps as a resource that the elementary school reps want to have, subject to certain rules (each elementary school rep needs the resource for a given length). This is no different than, say, considering buses as a resource that the routes want to have (for different amounts of time). It is, in other words, a rather common problem and there should be plenty of literature on finding efficient algorithms for this problem, as well as on which complexity class this problem falls into. (And no, sorry, I don't know the answer.)


Your description reminds me of the Knapsack problem, where the decision and optimization parts are NP-complete and NP-hard, respectively. The typical approach is to solve it using dynamic programming (memoization and greedy algorithms). Googling for knapsack scheduling also returns a lot of results (at least from my machine/ip). In wikipedia there is also a list of knapsack-like problems. Reducing your problem to one of those in the list is enough for proving NP-hardness.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.