Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite

Integer programing is one of the most narutal optimization tools.

As an analogy of DNF or CNF in the Boolean function theory, we can consider the following equation.

$x_{1}x_{2}x_{3}+$ $x_{3}x_{4}x_{5}+x_{1}x_{7}x_{9}=8,x_{i}\in \{0,1\}$

This constraint is not a linear one. However, every variables in any monomial has at most degree $1$.Call constraints of this kind $multi$-$lienar$ constraints.

We consider the following example as a instance of Multi-linear Integer($0$-$1$) programming, which is a system of multi-linear constraints.

$5x_{1}x_{2}x_{3}+2x_{3}x_{4}x_{5}+x_{1}x_{7}x_{9}=8$

$11x_{1}x_{3}+3x_{2}x_{4}x_{6}+23x_{3}x_{7}x_{8}+x_{10}=4$

$x_{2}x_{6}+4x_{3}x_{4}x_{5}+5x_{5}x_{7}x_{9}=4$

$x_{i} \in \{0,1\} $ Where all coefficients of each monomial is integer and polynomial order $n^{O(1)}$($n$ is the number of variables)

Solving Multi-linear 0-1 programming is deciding whether there exists an $0$-$1$ assingment which satisfies all of given multilinear constraints.

Ofcourse $0-1$ programming is a $NP$-complete problem in one of the 21 problems which R.Karp showed their completeness. More over Exponential Time Hypothesis seems to get rid of our hope to construct better sub-exponential time algorithms.

My question is :

Q

Are there any $slightly$ better exponential algorithm for Multi-linear 0-1 programming such as $2^{n-C\log n}$ time, $2^{n-C\log ^{2} n}$ times, or $2^{n-Cn^{0.001}}$ ?($C$ is a constant) ,and are there text-books or papers contains algorithms for integer programming of this type ?

share|improve this question
2  
It's sort of a funny question, in that "multi-linear 0-1 programming" reduces in linear time to regular (linear) 0-1 programming. E.g. $x_1x_2$ can be represented as $x_{12}$ with the additional constraints $x_{12} \ge x_1 +x_2 - 1$, $x_{12}\le x_2$, $x_{12} \le x_1$. So your question is very specific to the representation of the problem, in particular the number of variables. Also, do you intend all your constraints to be equalities? (Even with equalities one can model inequalities using slack variables, but this changes the number of variables.) – Neal Young Mar 19 at 16:48
2  
This paper says that this paper suggests that there is no $2^{\delta n}$-time algorithm for CNF-SAT for $\delta < 1$. I think CNF-SAT reduces to your problem (with inequalities) without increasing the number of variables. This is evidence that there is no $2^{\delta n}$-time algorithm for your problem as well. I realize that's a weaker result than you are asking for (you are asking about $2^{n-o(n)}$-time algorithms), but it's a start. – Neal Young Mar 19 at 17:13

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.