The CS170 MADS contest

Fall 2009

The Challenge:


The Maximum Average Dregree Subgraph problem (MADS) is this:  You are given a graph G = (V, E) and an integer k.  You are asked to find k nodes of G such that the number of edges M between these k nodes is as large as possible.  That is, the average degree d = 2M/k is as large as possible.

1.  Show that MADS is NP-complete (turn it into a search problem with parameters k and d).

2.  You are to write a program that solves MADS, that is, it finds a solution that is as good in as many situations as you can make it.  You can use any of the techniques for coping with NP-completeness that we know (branch-and-bound, approximation algorithms, local search, etc.).  You are going to do this in teams of up to 5 people.  Your program should be able to handle instances with 100 nodes and k = 50 (see 3 below).

3.  You are also going to submit an instance of the problem with 100 nodes and k = 50 that is, in your opinion, a hard one.  Your team's performance in this competition will be based on (a) how well your program does on the other teams' instances, and (b) how badly other programs do on your instance.  (The course instructors may or may not submit an entry.)  The winning team (the instructors' determination of the winner is final; the intructors' entry, if any, does not qualify to win) will get a copy of Logicomix and an embarrassing mention in Papa's homepage through January.



A.  This is worth one homework.  (Since you can drop homework grades, this means your participation is essentially voluntary.)

B.  There are many ways to game this.  For example, three teams may exchange bad instances and optimize on each other's to beat the rest.  These are all appallingly unsportsmanlike, and utterly unworthy of the spirit of CS170 this semester.

C.  1 and 3 are due Thursday Dec 10.  By Friday Dec 11 we'll make available the file of the instances your program will run on, and instructions on what to submit by Saturday Dec 12.


…And the Winners Are…


Amit 'Meatball' Assaf

Kyle Conroy

Jeff Hsu

Robert Wu

Wei Yeh


And here is the awards ceremony

(minus Kyle, seen here:




Runners up (so close it’s controversial):

Max Dama and Steven Hoyer