<p>Jukka's comment reminds me of the following reference.</p>

<p>If we look at such a function g as a matrix, the condition is equivalent to one in the definition of a permuted inverse Monge matrix.  There is a polynomial-time algorithm to determine if a given matrix is a permuted inverse Monge matrix (and if so, that gives corresponding permutations).</p>

<p>The result was found by Deineko and Filonenko (1979) in their Russian paper, and it is explained (in a more general form) in the following survey by Burkard et al.</p>

<ul>
<li>Rainer E. Burkard, Bettina Klinz, Rüdiger Rudolf: Perspectives of Monge Properties in Optimization. Discrete Applied Mathematics 70(2): 95-161 (1996) <a href="http://dx.doi.org/10.1016/0166-218X(95)00103-X" rel="nofollow">http://dx.doi.org/10.1016/0166-218X(95)00103-X</a></li>
</ul>

CC BY-SA 3.0
2011-10-20T06:35:53.077Z
Thnx! Definitely, I will read those papers. Indeed, I'm interested in the question is the set of permuted inverse Monge matrices a convex set. I hope after reading those paper I will now the answer on this.
Kostia Antoniuk
CC BY-SA 3.0
2011-10-20T01:42:22.663Z
2011-10-20T01:42:22.663Z
Yoshio Okamoto
<p>Let $K$ be an ordered finite set. Consider some function $g:K^2 \rightarrow R$ such that </p>

<p>$g(k1,k1&#39;) + g(k2,k2&#39;) \ge g(k1,k2&#39;) + g(k2,k1&#39;)$ </p>

<p>where $k1 &gt; k2$ (in order A1) and $k1&#39; &gt; k2&#39;$ (in order A2) (*)</p>

<p>Is there exists some effective algorithm which for given function can find such orders A1,A2 where the function fulfill  the property (*) or verify that such orders A1,A2 doesn't exists. </p>

<hr>

<p>REFORMULATION:</p>

<p>Let $K$ be a finite set.
Let $g\colon K^2 \rightarrow \mathbb{R}$.</p>

<p>We want to define the orders $&gt;_1$ and $&gt;_2$ on $K$ such that
$$s \, &gt;_1 \,\, t \text{ and } x \, &gt;_2 \,\, y$$ if and only if
$$g(s,x) + g(t,y) \ge g(s,y) + g(t,x).$$</p>

<p>Is there an efficient algorithm to prove the existence or non-existence of the two orders?</p>

CC BY-SA 3.0
2011-10-19T17:53:51.303Z
I have submitted an edit of the question so it is clearer (the way I understood it). If that was not the initial meaning of the question you can delete it: I have left your question untouched.
Gopi
CC BY-SA 3.0
2011-10-19T22:07:15.567Z
Yes, you understood it correctly!
Kostia Antoniuk
CC BY-SA 3.0
2011-10-19T22:33:39.930Z
It's worth noting that in the lattice induced by the product order of $A_1$ and $A_2$, the point $(k_2, k'_2)$ is the meet of $(k_1, k'_2), (k_2, k'_1)$ and the point $(k_1, k'_1)$ is the join. So actually your condition is merely the definition of supermodularity for $g$. So rephrased, your question is: Is there a way, for any function $g$, to construct a product lattice from two total orders so that $g$ is supermodular ?
Suresh Venkat
CC BY-SA 3.0
2011-10-19T22:55:38.217Z
In fact I'd recommend changing the title given this observation.
Suresh Venkat
CC BY-SA 3.0
2011-10-19T23:05:09.150Z
I'm concerned with "if and only if" in the REFORMULATION. For example, if g is a constant function, g is supermodular. But the condition in the REFORMULATION is not satisfied because for all 4-tuples (k1,k2,k1',k2') the inequality is satisfied (with equality).
Yoshio Okamoto
CC BY-SA 3.0
2011-10-19T23:35:20.813Z
Another interpretation might be this: can we permute the rows and columns of a matrix to make it "supermodular"? (Again, assuming that the "if and only if" part is wrong.)
Jukka Suomela
CC BY-SA 3.0
2011-10-20T06:29:51.477Z
Suresh Venkat, I have already asked about this here in terms of finding such permutations to make the problem submodular one, but nobody gave answer on this. Thus, I decided to make such formulation, and as you see, there is some answer given by Yoshio Okamoto.
Kostia Antoniuk
CC BY-SA 3.0
2011-10-20T06:33:08.803Z
Jukka Suomela, I think your interpretation is correct.
Kostia Antoniuk
CC BY-SA 3.0
2011-10-20T06:50:05.670Z
@KostiaAntoniuk: I see. but to be honest, your first question was very cryptic. This one makes more sense :)
Suresh Venkat
<co.combinatorics><permutations>
finding permutations which fulfills given conditions
Kostia Antoniuk
# finding permutations which fulfills given conditions

(Asked by: username_0 on 2011-10-18)

Let $K$ be an ordered finite set. Consider some function $g:K^2 \rightarrow R$ such that

$g(k1,k1') + g(k2,k2') \ge g(k1,k2') + g(k2,k1')$

where $k1 > k2$ (in order A1) and $k1' > k2'$ (in order A2) (\*)

Is there exists some effective algorithm which for given function can find such orders A1,A2 where the function fulfill the property (\*) or verify that such orders A1,A2 doesn't exists.

---

REFORMULATION:

Let $K$ be a finite set.
Let $g\colon K^2 \rightarrow \mathbb{R}$.

We want to define the orders $>\_1$ and $>\_2$ on $K$ such that
$$s \, >\_1 \,\, t \text{ and } x \, >\_2 \,\, y$$ if and only if
$$g(s,x) + g(t,y) \ge g(s,y) + g(t,x).$$

Is there an efficient algorithm to prove the existence or non-existence of the two orders?

**Tags:** co.combinatorics, permutations
> **Comments:**
> **username_1**: I have submitted an edit of the question so it is clearer (the way I understood it). If that was not the initial meaning of the question you can delete it: I have left your question untouched.  
> **username_0**: Yes, you understood it correctly!  
> **username_2**: It's worth noting that in the lattice induced by the product order of $A_1$ and $A_2$, the point $(k_2, k'_2)$ is the meet of $(k_1, k'_2), (k_2, k'_1)$ and the point $(k_1, k'_1)$ is the join. So actually your condition is merely the definition of supermodularity for $g$. So rephrased, your question is: Is there a way, for any function $g$, to construct a product lattice from two total orders so that $g$ is supermodular ?  
> **username_2**: In fact I'd recommend changing the title given this observation.  
> **username_3**: I'm concerned with "if and only if" in the REFORMULATION. For example, if g is a constant function, g is supermodular. But the condition in the REFORMULATION is not satisfied because for all 4-tuples (k1,k2,k1',k2') the inequality is satisfied (with equality).  
> **username_4**: Another interpretation might be this: can we permute the rows and columns of a matrix to make it "supermodular"? (Again, assuming that the "if and only if" part is wrong.)  
> **username_0**: Suresh Venkat, I have already asked about this here in terms of finding such permutations to make the problem submodular one, but nobody gave answer on this. Thus, I decided to make such formulation, and as you see, there is some answer given by Yoshio Okamoto.  
> **username_0**: Jukka Suomela, I think your interpretation is correct.  
> **username_2**: @KostiaAntoniuk: I see. but to be honest, your first question was very cryptic. This one makes more sense :)  

---

## 1 answers

### Answer by username_3 on 2011-10-20. Score: 4

Jukka's comment reminds me of the following reference.

If we look at such a function g as a matrix, the condition is equivalent to one in the definition of a permuted inverse Monge matrix. There is a polynomial-time algorithm to determine if a given matrix is a permuted inverse Monge matrix (and if so, that gives corresponding permutations).

The result was found by Deineko and Filonenko (1979) in their Russian paper, and it is explained (in a more general form) in the following survey by Burkard et al.

* Rainer E. Burkard, Bettina Klinz, Rüdiger Rudolf: Perspectives of Monge Properties in Optimization. Discrete Applied Mathematics 70(2): 95-161 (1996) <http://dx.doi.org/10.1016/0166-218X(95)00103-X>

> **Comments:**
> **username_0**: Thnx! Definitely, I will read those papers. Indeed, I'm interested in the question is the set of permuted inverse Monge matrices a convex set. I hope after reading those paper I will now the answer on this.  

---

