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