🚀 go-pugleaf

     In article <16017@megaron.cs.arizona.edu> johnk@cs.arizona.edu (John Kececioglu) writes:

  > I have four questions concerning algorithms for maximum weight
  > matchings in non-bipartite graphs.  (A matching is a selection of
  > edges from an undirected graph such that no two edges touch a common
  > vertex.)

  > First, what is the best known algorithm for computing a maximum weight
  > matching in a non-bipartite graph.  Here, best is with respect to
  > worst-case asymptotic time.

     I don't know about best for this problem, but I have been working
on fast algorithms for the problem on sparse bipartitie graphs and the
answers may be of some help.

     Assume you have nodes 1..i..n, edges 1..j..m, weight vector w,
and a matrix C of connections such that C\sub{ij} = 1 if edge j
touches node i, zero otherwise.  The the problem can be stated as:

     maximize \sum{i=1,n}{w\sub{i} x\sub{i}}
     subject to \sum{i=1,n}{C\sub{ij} x\sub{i} \le 1       all j
                x\sub{i} \ge 0                             all i

     (I tried to trade off between TeX rigor and readability...)

     This problem could be solved as a normal linear programming
problem, but it is usually much faster to solve a related problem.
Because it is much faster, you should probably solve the dual, then
use the Kuhn-Tucker conditions to recover x\sub{i}.  The dual is:

     minimize \sum{j=1,m}{u\sub{j}}
     subject to \sum{j=1,m}{C\sub{ij}u\sub{j}} \ge w\sub{i} all i
                u\sub{j} \ge 0                              all j

     In the bipartite case, I can transform the problem into an
Assignment Problem, then solve it by a variation of the Hungarian
Algorithm, but I don't see offhand how to do that here.  This problem
has the intuitive feel of being larger but simpler than the bipartitie
case, so you may want to do what I have done and develop a special
algorithm tailored to the problem.

  > Second, which matching algorithm is the best to implement on sparse
  > graphs of around 1000 vertices.  Here, best does not necessarily mean
  > simplest to program, but rather, fast in practise.

    A one thousand node problem takes about a second on a Sun-3, for
sparse matrices.  But I'm solving a different problem.  Solving the
dual above shouldn't take too long, and I think that you will have no
trouble recovering the primal variables, but it may take some work
(for my case a maximal flow problem) in this case it looks like
finding a solution among the edges for which C\sub{i,j} u\sub{j} = 0
for both end points.
    
    With sparse matrix techniques minutes should be easy, seconds
possible.  I'm dealing with sparse matrices (and as I say a somewhat
different problem).

  > Third, what is the best known algorithm for generating matchings in
  > decreasing order of weight for a non-bipartite graph.  Here, worst-case
  > asymptotic time is of interest.

    Huh?  I can't answer this question without knowing whether you
want all solutions or just the first k.  If the later, think about the convex
polytope corresponding to the feasible region of the primal problem.
Finding the other good solutions by pivoting will find keep finding
new "good" solutions and will allow you to generate a bound on the
best solution not yet seen.  When you have more than k better than the
best not seen, sort them and take the best k.

    If you need all solutions, this technique will find them, but
realize that that is a VERY big (exponential growth) number.


--

					Robert I. Eachus

with STANDARD_DISCLAIMER;
use  STANDARD_DISCLAIMER;
function MESSAGE (TEXT: in CLEVER_IDEAS) return BETTER_IDEAS is...