Notation: $\max( x_1, \cdots, x_n )$ denotes the maximal number among $x_1, \cdots, x_n$. $\min( x_1, \cdots, x_n )$ denotes the minimal number among $x_1, \cdots, x_n$.

Assumption: $x_i, a_i, b_k$ are all in $[0,1]$

minimize $\max( \{ \min(a_i, x_i) \mid i \in I\})$

$\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:

minimize $\max( \{ \min(0.2, x_1) , \min(0.8, x_3)\})$

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

What's the complexity of this problem?

  • $\begingroup$ The question is from linear programming. If one replaces + by max and * by min, the OP seems to be a very natural question. I suspect that there is a polynomial algorithm to solve this problem, but I could not obtain a very neat solution. Moreover I am wondering whether there is a general theory regarding this type of questions. $\endgroup$ – user124986 Jan 30 '14 at 15:59
  • $\begingroup$ These kinds of problems have a name... which I cannot for the life of me summon up. They are not linear programming problems, (see mathoverflow.net/questions/72735/…) and are harder than ordinary optimization problems. I will post again once I recall the name of the type of problem. $\endgroup$ – Jeff Snider Jan 30 '14 at 18:43
  • $\begingroup$ On the other hand, this answer suggests a way to linearize: stackoverflow.com/questions/10792139/… $\endgroup$ – Jeff Snider Jan 30 '14 at 18:44

On finding the maximum of $$\min(a_i, x_i).$$ Create extra variables $y_i$, add the constraints $$y_i\ge a_i, \text{ and } y_i\ge x_i,$$ and add one more variable $z$ plus the constraints $z\le y_i$ for all $i$. Your objective function is now $$z$$ which you want to maximize subject to the constraints.

This may not be a linear programming problem because the domain is non-convex, but a wide variety of solvers and techniques exist which can find the solution for you.


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.