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$
2
  • 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, 2014 at 2:27
  • 2
    $\begingroup$ @ChaoXu maybe post this as an answer ? $\endgroup$ Jan 30, 2014 at 16:35

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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