Problem
There are n students in a classroom. Every two
students are either enemies or friends. The teacher wants to divide the
students into two groups to work on a project while he leaves the classroom.
Unfortunately, putting two enemies in the same group will likely to lead to
bloodshed. So the teacher would like to partition the students into two groups
in a way that maximizes the number of enemies that belong to different groups.
Input
Data
We have n=750. This text file contains
the data about which two students are enemies or friends. The data file
describes an nxn matrix, where the ith row is
written in the ith
line of the file. Each line consists of a sequence of n 0’s or 1’s separated by a single space. If the (i,j) entry of the matrix is
a 1 then person i
and person j are enemies. If it is a
0 then they are friends.
Goal
- Try to find
a partitioning for which the number of enemies that belong to different groups
is large.
- Better yet,
let OPT denote the number of enemies in different groups in the best possible
partitioning. Try to find an interval [x,y]
for which you can guarantee that OPT lies in that interval. The interval should
be as small as possible.