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

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

<p><strong>Proof.</strong> 
If $x_i=y_i$ is a solution, then the system of $\max$ equations is feasible</p>

<p>Consider any solution, and $x_i &lt; 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\} &gt; 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\} &gt; b_k
$$.</p>

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

CC BY-SA 3.0
2014-01-30T17:24:34.297Z
2014-01-30T18:18:43.813Z
2014-01-30T18:18:43.813Z
Chao Xu
<p>Relating to <a href="https://cstheory.stackexchange.com/questions/20712/a-variant-of-linear-programming">a question I posted here</a>, I have formulated the following question:</p>

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

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

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

<p>for example: </p>

<p>$\max\{x_1, x_4\}=0.7$ and $\max\{x_1, x_2, x_3\}=0.5$</p>

<p>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?</p>

<p>Many thanks. </p>

CC BY-SA 3.0
2014-01-30T02:27:12.297Z
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.
Chao Xu
CC BY-SA 3.0
2014-01-30T16:35:35.360Z
@ChaoXu maybe post this as an answer ?
Suresh Venkat
<cc.complexity-theory><linear-programming>
Feasibility of equations with max constraints
maomao
# Feasibility of equations with max constraints

(Asked by: username_0 on 2014-01-29)

Relating to [a question I posted here](https://cstheory.stackexchange.com/questions/20712/a-variant-of-linear-programming), 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.

**Tags:** cc.complexity-theory, linear-programming

> **Comments:**
> **username_1**: 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.  
> **username_2**: @ChaoXu maybe post this as an answer ?  

---

## 1 answers

### Answer by username_1 on 2014-01-30. Score: 4

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.


---

