6
$\begingroup$

Suppose I have $n$ variables $x_1,\ldots,x_n$ that satisfy some inequalities that are highly symmetric, e.g., for all $S\subset [n], |S|=k$ we have $\sum_{i\in S} f(x_i,k)\le \sum_{i\in [n]} g(x_i,k)$, where $f$ and $g$ are some simple functions, e.g., composed of addition, minimum etc. Is there a polynomial algorithm to decide whether this system has an integer solution? What if the situation is a bit more complex, like we have several inequalities of the above form and/or additional individual inequalities, e.g., $x_i\le b_i$?

Motivation: Many classic problems can be brought to the above form, e.g., http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gallai_theorem and http://en.wikipedia.org/wiki/Fulkerson%E2%80%93Chen%E2%80%93Anstee_theorem. For example in Erdos-Gallai we have $f=x_i+\min(x_i,k)-(k-1)$ and $g=\min(x_i,k)$.

Seems related but I don't see a direct connection: http://arxiv.org/abs/1012.4941.

$\endgroup$
  • $\begingroup$ Does addition distribute over $f$ and $g$? $\endgroup$ – András Salamon Jan 21 '15 at 12:36
  • $\begingroup$ I am trying to see if there is some kind of algebraic structure. As far as I understand, you have addition as one operation, and $f/g$ as other operations. It then seems natural to ask whether $f(x)+f(y)=f(x+y)$, or even whether something like $f(x)+f(y)\ge f(x+y)$ always holds. $\endgroup$ – András Salamon Jan 21 '15 at 13:31
  • $\begingroup$ @András: I didn't have any such things in mind, but if you have a positive result using stronger assumptions, I am also interested. $\endgroup$ – domotorp Jan 21 '15 at 15:17
  • $\begingroup$ Taking the problem specification literally, it seems to me that the role of $S$ is unclear. Isn't the condition on $f$ and $g$ equivalent to $\forall i. f(x_i) \le g(x_i)$? $\endgroup$ – Neal Young Jan 25 '15 at 17:01
  • $\begingroup$ @Neal: Oops, I forgot that $f$ and $g$ can also depend on $|S|$, I hope it makes sense now. $\endgroup$ – domotorp Jan 25 '15 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.