Re: Problem on an nxn grid

Hah! This is actually for the "minimum-weight matching"
problem, with all non-negative weights.

An idea to speed up solution of some "weight matching"
problems where the weights vary considerably from each
other.

There are n matches (edges) in the solution set.

1. Sort the weights.
2. Call the sum of the n-1 lowest weights w_min.
3. Go through the weights from the lowest, selecting
the first n that don't disobey the selection criteria.
4. Sum this selection and call it ts_max.
4a. If ts_max = w_min + weight (low_n), you're done.
Lucky!
4b. Steps 3 and 4 might be repeated with variations
(such as rejecting the first weight out of hand) and
if the value is less than ts_max, it becomes ts_max.
5. Any weight greater than ts_max - w_min cannot be
part of the solution set.
6. Use your favourite algorithm on remaining weights.

--
Jonathan Berry

.

Relevant Pages

  • Re: "hat" container class [C++]
    ... >> probability distribution defined by the given weights. ... > selection from a changing client list, ... special case of a fixed set of options with non-changing weights. ...
    (comp.lang.cpp)
  • FA: France kiloware COMMEMORATIVE with 2007 + HV
    ... Up for auction on ebay, ... weights 100 grams. ... Great selection, low duplication. ...
    (rec.collecting.stamps.marketplace)