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.