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?

Improve this question
$\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
    Commented Oct 19, 2011 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
    Commented Oct 19, 2011 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
    Commented Oct 19, 2011 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
    Commented Oct 19, 2011 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
    Commented Oct 20, 2011 at 6:50

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Oct 20, 2011 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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