Re: Problem on an nxn grid

On May 11, 3:08 pm, "guolij...@xxxxxxxxx" <guolij...@xxxxxxxxx> wrote:
On May 11, 2:31 pm, Robert Israel



<isr...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:
Jonathan Berry <jbe...@xxxxxxxxxxxxx> writes:
An nxn grid is filled with positive integers. I want a practical way
(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!

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...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada- Hide quoted text -

- 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.- Hide quoted text -

- Show quoted text -

I'm sorry, You are right, Robert Israel. Every maximum-weight clique
can reduce to this problem. I made a mistake.

.

Relevant Pages

  • Re: Problem on an nxn grid
    ... to select n/2 integers from the grid such ... So, for example, if the grid entry at (3, ... weight clique problem, but I think not every maximum-weight clique ...
    (sci.math)
  • Re: Problem on an nxn grid
    ... to select n/2 integers from the grid such ... So, for example, if the grid entry at (3, ... This can be considered as a maximum-weight clique problem. ...
    (sci.math)
  • Re: Problem on an nxn grid
    ... 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 ... So, for example, if the grid entry at (3, ...
    (sci.math)
  • Re: Problem on an nxn grid
    ... to select n/2 integers from the grid such ... that the sum of the integers is the smallest. ... So, for example, if the grid entry at (3, ... This can be considered as a maximum-weight clique problem. ...
    (sci.math)
  • Problem on an nxn grid
    ... An nxn grid is filled with positive integers. ... 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 ...
    (sci.math)