polynomial time algorithm

The problem is as follow:

we have n variables x_1, x_2, ... x_n

and m triples t_1, t_2, ... t_m

each triple contain three distinct variables for example t_1 = {x_1, x_3, x_5}

An assignment is to assign all variables value either 0 or 1. An triple is called active if all variables has the same value. say if t_1 = {x_1, x_3, x_5} and the assignment assigns x_1 x_3 and x_5 value of 0 then t_1 is active.

Then we need to find a assignment to minimize the number of active triples.

I can think about an non polynomial time algorithm that is to start from an arbitrary assignment and then start to check from x_1 to x_n. if we flip x_k it leads to a less number of active triples then we do it and start to check from the beginning again. It ends when we can not flip any x_k.

But there should be an polynomial time algorithm for this problem. Can anyone help me with this? Thanks in advance!!

Quote:

---

Originally Posted by Jake2011

But there should be an polynomial time algorithm for this problem.

---

With some effort this problem probably can be formulated as a 0-1 Integer Programming problem similar to the 0-1 Knapsack problem. And from what I can see here,

http://en.wikipedia.org/wiki/Knapsack_problem

this problem can be solved in pseudo-polynominal time using a dynamic programming approach.

Since I've already given this some thought I can as well post my suggestion for a solution.

All variables are 0-1.

First introduce a tripple evaluation function,

f = a*b*c + (1-a)*(1-b)*(1-c)

It evaluates to 1 when all variables are equal (when a=b=c=1 or a=b=c=0) othwerwise it evaluates to 0.

Let f=1 correspond to an active tripple and f=0 to a passive. The objective is to have as few active tripples as possible and this can be expressed as:

Minimize the sum of all f.

This is a non-linear problem (because the variables are multiplied in the f evaluations). Can it be made linear? I think so.

Introduce two new variables and make the following substitutions,

x = a*b*c
y = (1-a)*(1-b)*(1-c)

which gives this new tripple evaluation function,

f = x + y

bound by these conditions,

a + b + c - 2*x <= 2 // enforces x=1 when a,b,c are all 1
-a - b - c + 3*x <= 0 // enforces x=0 when a,b,c are NOT all 1
-a - b - c - 2*y <= -1 // enforces y=1 when a,b,c are all 0
a + b + c + 3*y <= 3 // enforces y=0 when a,b,c are NOT all 0

(note that when a value isn't enforced the condition is don't care)

and the objective still is to:

Minimize the sum of all f.

This is now a 0-1 linear integer programming problem very similar to the 0-1 Knapsack problem. The differences should be easily handled if a dynamic programming solving approach is used. The promise then is that a solution can be found in pseudo-polynominal time.

The downside is that the linearization comes at a cost. For each tripple two variables and four conditions must be introduced.

Hi,

if you are satisfied with a very good solution and you do not require to be shure that you found the absolute optimum, then try an genetic algorithm.


GMarco