／var／logmarcus chiu

Randomized Rounding

Created on

the randomized rounding technique works the best when the ILP is of combinatorial nature, that is, a 0-1 programming problem

consider the 0-1 problem:

0-1 Problem

  • objective function:
    max Z = cx
  • linear constraints:
    Ax = b
  • 0-1 variables:
    xi∈ {0, 1}, for i = 1, …, n

relax the 0-1 Problem by replacing the last constraint with 0 ≤ xi≤ 1

Relaxed LP Problem

  • objective function:
    max Z = cx
  • linear constraints:
    Ax = b
  • 0-1 variables:
    0 ≤ xi≤ 1, for i = 1, …, n

this new problem is called the LP relaxation of the 0-1 program

TODO