Problem on an nxn grid
Jonathan Berry
(for large n, say up to 300) to select n/2 integers from the grid such
that the sum of the integers is the smallest.
The limiting factor on the selection is that each coordinate from 1 to
n is used exactly once. So, for example, if the grid entry at (3,
149) is one of the integers, no other selection may be of the form (3,
y) nor (x, 149), nor (x, 3), nor (149, y).
I'll have a computer to do the crunching, but when I considered the
"brute force" method of just trying every combination, it looked like
n! / (n/2)! operations, so the computer and I could be waiting a long
time. 42, and all that.
For example? A 6x6 grid, the smallest sum of
3 elements
1 5 8 2 1 3
2 9 7 3 4 5
1 6 7 2 4 2
3 2 5 1 3 1
8 6 2 1 4 2
3 2 7 4 1 1
Numbering from the left and top, a solution is
(5, 1) + (2, 6) + (4, 3) =
1+2+1 = 4.
No numbers on the diagonal (such as (1,1), (4,4), or (6,6)) can be
selected, because that would contradict the condition that each
coordinate can be used only once. So the value of any (a,a) number on
the grid is irrelevant.
Believe it or not, this is a model of a practical problem!
TIA.
--
Jonathan Berry
Gerry Myerson
Jonathan Berry <jbe...@islandnet.com> wrote:
There's something called The Assignment Problem, which differs
from your problem in that once you've picked (3, 149) you can still
pick (x, 3) and/or (149, y), but not the other two guys you forbid.
There's an efficient algorithm for solving it, called The Hungarian
Method.
There may be a way to transform your problem into an instance
of The Assignment Problem, perhaps at the cost of going to
a 2 n by 2 n grid.
--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
Robert Israel
This can be considered as a maximum-weight clique problem. The
non-diagonal points of your grid correspond to vertices of a graph,
with weights given by your integer entries, and an edge joining
each pair of points that have all different coordinates. The
maximum-weight clique problem is NP-hard, but there are a number of
algorithms that turn up in a Google search.
--
Robert Israel isr...@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
guol...@gmail.com
>
> - Show quoted text -
I don't agree with your, through this problem can reduce to a maximum-
weight clique problem , but I think not every maximum-weight clique
problem can reduce to this problem.
guol...@gmail.com
>
> - Show quoted text -
I'm sorry, You are right, Robert Israel. Every maximum-weight clique
can reduce to this problem. I made a mistake.
Ioannis
news:1178860600.0...@e65g2000hsc.googlegroups.com...
[snip]
> I'm sorry, You are right, Robert Israel. Every maximum-weight clique
> can reduce to this problem. I made a mistake.
What is the difference between a novice/putz/mazetta (or however you want to
call a bad) chess player and a grandmaster in hanging their queens?
None. Both hang their queens, the difference is in the frequency: A mazetta
will hang his queen 20 times in 50 games. A grandmaster will hang his queen 1
time in 1000 games.
The probability of Robert making a mistake is of the same order as that of a
grandmaster hanging his queen.
--
I.N. Galidakis --- http://ioannis.virtualcomposer2000.com/
----------------------------------------------------------
"There's ALWAYS a mistake somewhere"
Robert Israel
I didn't claim that every maximum-weight clique problem can be reduced
to this one, so I'm neither right nor wrong on that. How do you make
that reduction?
asinop
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
Chip Eastham
It's an interesting problem, so I admit it's a petty
observation to point out that your solution of the
example problem is incorrect. It is customary
to provide the row coordinate first and column
coordinate second, but for consistency I'll try
to use your notation.
You say the grid entries are numbered from the
top and left, so presumably your (5,1) entry
is claimed to be 1 based on the 5th column,
1st row being 1. Likewise the claim of (2,6)
entry being 2 appears to correspond to 2nd
column and 6th row. But neither (4,3) entry
interpreted as 4th column, 3rd row nor vice
versa contains an additional 1 (though a 2
appears in the 4th column and 3rd row).
Perhaps you had these entries in mind
which give a minimal sum of 4:
1st col, 3rd row = 1
2nd col, 4th row = 2
5th col, 6th row = 1
The minimal solution is not unique, for example:
1st col, 3rd row = 1
2nd col, 6th row = 2
4th col, 5th row = 1
A slightly more useful observation: Without
loss of generality, you may symmetrize the
grid by replacing A(i,j) by the least of A(i,j)
and A(j,i) for all distinct i,j. This follows
from the observation that in any feasible
choice of n/2 entries, replacing A(i,j) by
A(j,i) is again feasible (no duplicated
coordinates).
It appears that branch and bound methods
for these problems will be effective. If you
have a "real world" size problem you'd like
me to tackle, email me and I'll try a quick
Prolog program on it.
regards, chip
Chip Eastham
Very elegant! You've clearly shown the equivalence
of these two classes of problems.
regards, chip
Jonathan Berry
Thank you, Chip, for so gently pointing out the drawbacks in
my analysis of the example. I saw 2 at (4,3), but typed
1. Then I overlooked that there were two "other" solutions.
Kind of like a chess player giving away the queen, then both
rooks, in the same game. Or to warp another saw, "Make
up an example on the fly, then ... live with it".
I am not sure that your observation about symmetrizing
the grid is helpful to me. In the application that I have in mind
(which is the pairing of chess tournaments!), the important
part is the coordinates (and ij is importantly different from ji), not
in the value of the cells nor in the value of the sum, except that it
be minimized.
It is slightly concerning that there may be more than one solution,
but if larger numbers are used, then that becomes less likely.
Thank you, but I'll hold off on your offer of writing a Prolog program
for now. I'm trying to get everything under one "roof",
in PowerBASIC. But I may be out of my depth here. So
"for now" may be very short.
I only partly understood the algorithm described by Ali (Asinop). I'm
OK until:
"- 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."
I'd need to learn what graph, node, weight, and (maximum) weighted
matching are. And then translate that into plodding computer code.
Ironically, I do hold a Math bachelor's from the same institution
where Robert Israel teaches. You might call it a "No-More Analysis-My-
Head-Hurts" degree. Likely to his credit, my degree was granted while
he was still at Princeton.
--
Jonathan Berry
Chip Eastham
A reference that I have to hand for this sort of stuff is:
Algorithmic Graph Theory, by Alan Gibbons
Cambridge University Press, 1985
a slender paperback volume that addresses both
theory and algorithmic issues. Chapter 5 is on
matchings (selecting edges of a simple graph so
that no node appears more than once), and Sec.
5.3 is on maximum-weight matchings and an
algorithm for these problems proposed by
Edmonds and Johnson:
Edmonds, J. and Johnson, E.
"Matching: A well-solved class of integer linear
programs", Combinatorial Structures and Their
Applications, Gordon & Breach, NY
pp. 89-92, 1970
Your application may still depend on distinguishing
A(i,j) and A(j,i), since you can always discern the
least of these after the fact of solving the reduced
problem, as proposed by asinop as well, that
considers only a minimum sum using the lesser
of each pair. You're only setting the information
aside, not ignoring any distinction important in
your application.
regards, chip
Jonathan Berry
"See Spot Run" in the vocabulary of Graph Theory.
Sparing everyone the litany of that journey...
Thanks very much to every poster, especially Chip,
Asinops and Robert Israel, for their help.
The problem is a "maximum-weight matching" with n up to
around 300. Does there exist code (or better, pseudo-code)
to solve this? It could be argued that Chapter 5.3 of
Gibbons's "Algorithmic Graph Theory" gives a pseudo-code
for the Edmonds algorithm, but it is couched in, er,
Graphic, language. As, for the purposes of this discussion,
a lukewarm mathematician, and a lukewarm coder, it looks
daunting. Indeed, I have mined google, and although there
seems to be something approaching pseudo- code for related
problems (such as the Stable Roommate Problem) and code for
parts of the Edmonds algorithm (such as the Hungarian
algorithm), I could not find code or pseudo-code for the
whole kahuna, an algorithm which solves the maximum-weight
matching problem in polynomial time. Maybe I haven't looked
in the right places. But an email from one of you confirms:
no readily- available code.
I'm guessing that the reason will be that it is "too easy".
Too easy a subject for a degree thesis, that is.
Anyway, if somebody can point me to pseudo-code, I'd
appreciate it.
In a separate post, I will put forward an idea that might
not reduce the big-O Order of working this through by brute
force, but might reduce the real-world CPU time in cases
where the values (weights) are not overly close to each
other.
--
Jonathan Berry
Jonathan Berry
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
Chip Eastham
Hi, Jonathan:
My last post to this thread seems to have gone missing,
an all too frequent event with Google Groups. Below I
will refer to the weight of edge from node i to node j
as A(i,j), consistent with the earlier grid/matrix
notation in this thread. All weights are assumed to be
nonnegative. We seek a minimum (total) weight perfect
matching of the (underlying) complete graph on n nodes.
This paper:
http://www.dcg.ethz.ch/publications/ctw04.pdf
by Wattenhofer and Wattenhofer gives pseudo-code
for two approximation algorithms assuming that the
weights of the graph satisfy the triangle inequality,
i.e. A(i,j) <= A(i,k) + A(k,j) for all nodes i,j,k.
This restriction is in one sense inessential as
adding max(A) to every weight forces that condition
to be true but at the expense of messing up the
approximation property (because it now applies to
the total inflated by max(A) * n/2).
It suggests the question of whether exact solutions
for weighted graphs satisfying triangle inequalities
can be found just as efficiently, e.g. with nearly
quadratic algorithms rather than the improvement of
Edmonds original O(n^4) to O(n^3) by Gabow (and in
an earlier paper by Lawler).
Although most implementation details are omitted, a
helpful discussion of the history and tests is here:
http://www2.isye.gatech.edu/~wcook/papers/match_ijoc.pdf
in a paper by Cook and Rohe. If the weights can be
realized as the Euclidean distances between nodes
assigned coordinates, then the problem is said to be
"geometric", and of course the weights must then
satisfy the triangle inequality condition.
It is known that an exact solution can be obtained
in near quadratic time if the coordinates are in a
plane:
www.cs.brown.edu/cgc/cgc98/final/final21.ps
by divide and conquer techniques.
regards, chip