Suppose we have a $n\times n$ symmetric matrix $\mathbf A$.

I want to know if there exists two elements of a vector $\mathbf x$, let's call them $x_i,x_j,i\ne j$, such that $x_i +x_j+[A]_{i,j}\ge y$ for some vector $\mathbf x$ of size $n$. So:

$$ f\left(\mathbf x \in \mathbb N^n,y\right)= \begin{cases} 1&\text{if }\exists_{i,j,i\ne j}x_i+x_j+[A]_{i,j}\ge y\\ 0&\text{otherwise}\\ \end{cases} $$

We can alternatively formulate it simpler, by subtractiong $\frac y 2$ from all $x_i \in \mathbf x$, and flip the sign of the elements $\mathbf A$ and formulate it like this:

$$ g\left(\mathbf x \in \mathbb N^n\right)= \begin{cases} 1&\text{if }\exists_{i,j,i\ne j}x_i+x_j\ge [A]_{i,j}\\ 0&\text{otherwise}\\ \end{cases} $$ $\mathbf A$ does not have to be stored as a matrix, and I am hoping some other form of storage can help here - some sort of precomputation.

Is there an efficient algorithm for this (subquadtratic in $n$)?

I am sort of struggling to name this, so:

Is this a known problem, or reducible to a known problem?


Here is one approach that might offer some improvements for some matrices $A$. However, I don't expect it will lead to an algorithm whose worst-case running time is subquadratic, so your question remains open.

Let's characterize the set of $\mathbf{x}$ for which $g(\mathbf{x})=0$. This happens exactly if $x_i+x_j < A_{i,j}$ holds for all $i,j$. Notice that this gives us a set of $n(n-1)/2$ linear inequalities (one for each $i,j$) in $n$ unknowns (the $x_1,\dots,x_n$). They define a convex polytope $\mathcal{P}$ in $n$ dimensions.

Your problem then reduces to the following: given $\mathbf{x}$, test whether $\mathbf{x} \in \mathcal{P}$. I don't know whether there are any algorithms for testing membership in a convex polytope (defined as the intersection of halfspaces) more efficiently than separately testing whether the point is contained in each halfspace, but that's something you could investigate.

As a simple optimization, it is easy to identify a minimal subset of those linear inequalities that generate the same polytope. For each linear inequality, you can test whether it is redundant (implied by the other linear inequalities) using linear programming. If it is, delete that redundant linear inequality and continue trying to minimize the set. If you're able to reduce the set of linear inequalities to $m$ inequalities, then you can classify any given vector $\mathbf{x}$ in $O(m)$ time. However, I don't see any reason to expect that in general you will be able to remove enough inequalities to make this run in subquadratic time (I don't see any reason to necessarily expect that more than a constant fraction of the linear inequalities will be redundant).

Incidentally, here's a variant of your problem which might be easier to think about. Suppose we have a symmetric matrix $D$, and given a vector $\mathbf{x}$, we want to test whether $x_i - x_j < D_{i,j}$ for all $i,j$. Let $h(\mathbf{x})=1$ if there exists $i<j$ such that $x_i - x_j \ge D_{i,j}$ and $h(\mathbf{x})=0$ otherwise. This problem looks much like your original problem, except with subtraction instead of addition.

This problem might be a little easier to think about, because this system of difference equations can be expressed as a difference graph. Build a directed graph whose vertices are the indices, and where the edge $i \to j$ is labelled with $D_{i,j}$. Each edge in the graph corresponds to a linear inequality; e.g., the edge $i \stackrel{d}{\to} j$ corresponds to the inequality $x_i - x_j < d$. Consequently, each path also corresponds to a linear inequality: e.g., $i \stackrel{d}{\to} j \stackrel{d'}{\to} k$ corresponds to $x_i - x_k < d+d'$, so given a difference graph, you can construct its transitive closure (for each pair of edges $i \stackrel{d}{\to} j \stackrel{d'}{\to} k$, replace the edge $i \stackrel{d''}{\to} k$ by $i \stackrel{d^*}{\to} k$ where $d^* = \min(d+d',d'')$).

Now if you take the transitive reduction of the difference graph corresponding to $D$, you get a minimal set of non-redundant linear equations that characterize the set of vectors $\mathbf{x}$ such that $h(\mathbf{x})=0$. If the transitive reduction of this graph has $m$ edges, then you can test whether $h(\mathbf{x})=0$ in $O(m)$ time. However, I don't see any reason to expect that every graph will have a transitive reduction that is subquadratic in size, so this is probably another dead end.

  • $\begingroup$ Interesting variant. I'll to think on that. $\endgroup$ – Realz Slaw Nov 12 '13 at 1:29

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.