1
$\begingroup$

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?

$\endgroup$
9
  • 2
    $\begingroup$ 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. $\endgroup$ – Gopi Oct 19 '11 at 17:53
  • 2
    $\begingroup$ 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 ? $\endgroup$ – Suresh Venkat Oct 19 '11 at 22:33
  • 3
    $\begingroup$ 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). $\endgroup$ – Yoshio Okamoto Oct 19 '11 at 23:05
  • 3
    $\begingroup$ 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.) $\endgroup$ – Jukka Suomela Oct 19 '11 at 23:35
  • 1
    $\begingroup$ @KostiaAntoniuk: I see. but to be honest, your first question was very cryptic. This one makes more sense :) $\endgroup$ – Suresh Venkat Oct 20 '11 at 6:50
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Kostia Antoniuk Oct 20 '11 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.