1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Finding an approximation algorithm

  1. Nov 12, 2009 #1
    For a class project, I need to make an application that, among other things, can sort students in a class into project teams that takes students' schedules into consideration and groups students with overlapping schedules together.

    The way I'm storing schedule data is a collection of times which the student is free. There are 21. Morning, afternoon, evening for 7 days.

    This way, students' schedules can be expressed as subsets of that set of 21 possible free times. For example {mondayAfternoon, saturdayEvening} and {tuesdayMorning, fridayAfternoon, wednesdayMorning} could all be subsets.
    From that perspective, I'm looking at finding intersection of k subsets (where k is an arbitrary number of teams) such that the cardinality of their intersection is maximized.

    Mainly I'm wondering if there is a common NP problem with an approximation algorithm that I can examine to possibly implement.

    I've already implemented a solution that involves distributing the students with high and low free times evenly among teams to minimize the chance of teams having clusters of students with no free time. This isn't really a great solution, but it is at least some way of sorting by schedule.

    So my interest in finding a better algorithm is mainly driven by a geeky desire to make a better program and also learn about these kind of problems (I'm a CS undergrad, haven't taken theory of computation or anything yet).

    I would appreciate any pointers.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted