finding permutations which fulfills given conditions Let $K$ be an ordered finite set. Consider some function $g:K^2 \rightarrow R$ such that 

$g(k1,k1&#39;) + g(k2,k2&#39;) \ge g(k1,k2&#39;) + g(k2,k1&#39;)$ 

where $k1 &gt; k2$ (in order A1) and $k1&#39; &gt; k2&#39;$ (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 $&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).$$

Is there an efficient algorithm to prove the existence or non-existence of the two orders?
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