Under Construction

(2VIP) Two VARIABLE INTEGER PROGRAMMING
Instance: A set of 2 variables linear constraints.
          Each variable has integer interval constraint.
          Each variable i has linear weight function
          s.t. Wi(x)>=0 for all assignment x in the i'th interval.
Solution: A satisfying assignments X={x1,...xn} of all variables.
Measure : W(X) (i.e. Sum {Wi(xi): i in {1,...,n}})

+------------------------------------------------------------------+
|   The "Local-Ratio Theorem" (oriented for 2-VIP)                 |
+------------------------------------------------------------------+
|   If   X is 2-approximation 2VIP w.r.t the weight function W1    |
|   and  X is 2-approximation 2VIP w.r.t the weight function W2    |
|   then X is 2-approximation 2VIP w.r.t the weight function W1+W2 |
+------------------------------------------------------------------+

We recommend to visit the 2SAT page.

+-----------------------------------------------------------------+
|Before starting, verify that feasible solution exists [Bar-yehuda&Rawitz99]
|Now as long as there exists x with interval [l,u] s.t l<u:
|   Partition [l,u] into two non empty intervals [l1,u1],[l2,u2]
|   case:
|      x in [l1,u1] leads to a contradiction: assign [l,u]=[l2,u2]
|      x in [l2,u2] leads to a contradiction: assign [l,u]=[l1,u1]
|      x in [l1,u1] leads to a interval
         changes that "costs" 0 w.r.t. W    : assign [l,u]=[l1,u1]
|      x in [l2,u2] leads to a interval
         changes that "costs" 0 w.r.t. W    : assign [l,u]=[l2,u2]
|      Otherwise (the Local-Ratio Step):
|        Find any W1 s.t. W1<=W and
              the cost of the impact x in [l1,u1] is equal to
              the cost of the impact x in [l1,u1] w.r.t. W1;
|        W=W-W1;
+-----------------------------------------------------------------+

For more details see the paper by Rawitz and myself.