match/match.git
15 years agoRewrite Bellman-Ford and min-cost flow, especially to stop the latter from crashing.
Matt McCutchen [Fri, 11 Jul 2008 03:46:07 +0000 (23:46 -0400)]
Rewrite Bellman-Ford and min-cost flow, especially to stop the latter from crashing.

- Rewrite Bellman-Ford and min-cost flow solvers using the state-transformer
  feature, adding infrastructure as necessary.
- Make Bellman-Ford detect the presence of a negative cycle.
- Min-cost flow now uses edges of arbitrary capacity, not just 1, although it's
  the same naive algorithm that augments along the lowest-cost path no matter
  how little flow that adds.  Adjust the reduction accordingly; now it uses
  fewer edges.  Additional benefit: the change brings my min-cost flower's
  interface closer to that of an eventual CS2 adaptor.
- Min-cost flow was crashing on larger instances because round-off error
  prevented it from identifying the edge to be flipped by subtracting the costs
  to its endpoints.  To avoid this problem, redesign min-cost flow so edges are
  identified by unique indices.  Now doMatching "pulls" flow values for the
  edgesD it generated instead of being "pushed" by edges in the residual graph.
- Make the Show implementation for Instances prettier.

15 years agodebug needs -fglasgow-exts too.
Matt McCutchen [Fri, 11 Jul 2008 03:29:31 +0000 (23:29 -0400)]
debug needs -fglasgow-exts too.

15 years agoThe random instance generator and other improvements.
Matt McCutchen [Thu, 10 Jul 2008 19:23:46 +0000 (15:23 -0400)]
The random instance generator and other improvements.

- Split Instance into its own file, change it to use arrays, and implement Show.
- Add random InstanceGenerator using RandomizedMonad.
- Make Test export more stuff for use from GHCi.

15 years agoSecond version of the reduction.
Matt McCutchen [Mon, 7 Jul 2008 23:37:31 +0000 (19:37 -0400)]
Second version of the reduction.

Significant changes:
- Supports a per-reviewer relative load limit, which is hard with a tolerance.
- Split each reviewer into multiple nodes in order to charge a cost quadratic in
  the number of disliked proposals she has to review.  Previously, cost was
  simply additive.
- Require three reviews per proposal regardless of experts, but provide an
  incentive for a knowledgeable review and an additional expert review.

Also, add import and "show-graph" script for graph visualization.

15 years agoFix bug in second-pass graph construction when a proposal got more than one expert...
Matt McCutchen [Mon, 7 Jul 2008 23:30:05 +0000 (19:30 -0400)]
Fix bug in second-pass graph construction when a proposal got more than one expert review.

15 years ago- Add the notes Samir emailed me on 2008-07-06.
Matt McCutchen [Sun, 6 Jul 2008 15:32:52 +0000 (11:32 -0400)]
- Add the notes Samir emailed me on 2008-07-06.
- Move the program into a subdirectory to cut down on rebuilding.
- Hide the .git contents from Eclipse.

15 years ago- ./debug and ./run now pass along arguments.
Matt McCutchen [Mon, 23 Jun 2008 22:03:07 +0000 (18:03 -0400)]
- ./debug and ./run now pass along arguments.
- Add ./make-package .

15 years agoThe proposal matcher. It works on a small example.
Matt McCutchen [Mon, 23 Jun 2008 21:55:09 +0000 (17:55 -0400)]
The proposal matcher.  It works on a small example.