|Start Page Number:||699|
|End Page Number:||725|
|Publication Date:||Nov 2011|
|Journal:||Journal of Combinatorial Optimization|
|Authors:||Ye Yinyu, Zhang Jiawei, He Simai, Ge Dongdong|
|Keywords:||graphs, programming: integer|
We develop a new dependent randomized rounding method for approximation of a number of optimization problems with integral assignment constraints. The core of the method is a simple, intuitive, and computationally efficient geometric rounding that simultaneously rounds multiple points in a multi‐dimensional simplex to its vertices. Using this method we obtain in a systematic way known as well as new results for the hub location, metric labeling, winner determination and consistent labeling problems. A comprehensive comparison to the dependent randomized rounding method developed by Kleinberg and Tardos (2002) and its variants is also conducted. Overall, our geometric rounding provides a simple and effective alternative for rounding various integer optimization problems.