1
$\begingroup$

Relating to a question I posted here, I have formulated the following question:

Notation: $\max\{ x_1, \cdots, x_n \}$ denotes the maximal number among $x_1, \cdots, x_n$.

How to check the following system of equations is feasible? Assumption: $x_i, b_k$ are all in $[0,1]$

$\max\{x_i\mid i\in J_k\}=b_k$ where $1\leq k\leq m$ and $J_k\subseteq \{1, \cdots, n\}$

for example:

$\max\{x_1, x_4\}=0.7$ and $\max\{x_1, x_2, x_3\}=0.5$

What's the complexity of this problem? Obviously it is in NP, but is it NP-hard? It would be a surprise if such an easy problem does not have a polynomial algorithm. Does linear programming help here?

Many thanks.

$\endgroup$
  • 4
    $\begingroup$ If I'm not missing anything, the system of $\max$ equation is feasible iff $x_i=\min\{b_k| i\in J_k\}$ is a solution, thus it admits a linear time algorithm. $\endgroup$ – Chao Xu Jan 30 '14 at 2:27
  • 2
    $\begingroup$ @ChaoXu maybe post this as an answer ? $\endgroup$ – Suresh Venkat Jan 30 '14 at 16:35
4
$\begingroup$

Let $y_i=\min\{b_k| i\in J_k\}$. Observe for any feasible solution, $x_i\leq y_i$.

Claim: The system of $\max$ equations is feasible iff $x_i=y_i$ for $1\leq i\leq n$ is a solution.

Proof. If $x_i=y_i$ is a solution, then the system of $\max$ equations is feasible

Consider any solution, and $x_i < y_i$ for some $i$. We can increase $x_i$ to $y_i$ without violate any equation. Assume it violates the $k$th equation, namely $\max\{x_j|j,i\in J_k\}=b_k$, then it implies $y_i = \max\{x_j|j,i\in J_k\} > b_k$, but that's a contradiction because $$ b_k \geq \min\{b_j| i\in J_j\} = y_i = \max\{x_j|j,i\in J_k\} > b_k $$.

The algorithm is just compute $y_i$s and check if it satisfies all the equations. This takes linear time.

$\endgroup$

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.