MaxCut: student notebook
MaxCut asks you to split the nodes of a graph into two groups so that as many edges as possible
run between the groups. You write the split as a partition, one 0 or 1 per node, and the number of
edges running between the groups is its cut.
The data. The 50 training graphs (julian/pq-example-training) come with their optimal cut and one
optimal partition, so you can score yourself here. The 50 test graphs (julian/pq-example-test) come
without them: only the leaderboard knows their answers. Every graph is small (7 to 20 nodes),
unweighted and connected.
Clone this workspace first
Press Clone on this workspace's page and work in your copy. Your results are saved to the aqora store
of the workspace's owner: in Julian's copy they would land in Julian's store, and the leaderboard would
find nothing in yours.
How it works
- Clone this workspace.
- Replace
solve below with your own solver.
- Check your training score. It updates every time you change
solve.
- Press Run on the test set and save at the bottom.
- Open the leaderboard, sign in and press Submit.
Scoring. Each graph scores your cut divided by its optimal cut, and your score is the mean over all
graphs. Random partitions score about 0.67, a one-flip local search (flip single nodes while that grows
the cut) about 0.94, and the optimum is 1.0.