Re: Problem on an nxn grid

On May 11, 11:42 am, asinop <asi...@xxxxxxxxx> wrote:
You can formulate this problem as an instance of maximum weighted
matching on general graphs, which has efficient polynomial solvers.
The algorithm is:

- You first bring the matrix to upper triangular form (for every (i,j)
(i<j), a'_{ij} = M-min(a_{ij},a_{ji}), where M is a big number st
a'_{ij}>=0.
- Then form a graph with n nodes representing coordinates. Place edges
between nodes i and j (i<j) with weight a'_{ij}.
- Do maximum weighted matching on this graph.

Hope this helps.

Ali

Very elegant! You've clearly shown the equivalence
of these two classes of problems.

regards, chip

.

Relevant Pages

  • Re: Problem on an nxn grid
    ... matching on general graphs, ... You first bring the matrix to upper triangular form ... Then form a graph with n nodes representing coordinates. ...
    (sci.math)
  • Graph Matching Genetic Algorithms
    ... I m planning to develop a genetic algo based graph matching. ... the input graph is a region adjacency graphwith feature vector ...
    (comp.ai.genetic)
  • entering matching data for line charts
    ... In Excel 2003 I'm trying to construct a line graph ... in which there is is more than one set of matching x and y values. ... If I were drawing a scatter plot, I could enter matching x and y values, but ...
    (microsoft.public.excel.charting)
  • Re: Finding the Maximum Number of Node-disjoint Cycles
    ... What format should I use to describe the graph? ... in principle it's easy to read and convert other formats. ... >G has a disjoint cycle cover if and only if H has a perfect matching. ...
    (comp.theory)