Optimization Online


Geometric Rounding: A Dependent Rounding Scheme for Allocation Problems

Dongdong Ge(dongdong***at***stanford.edu)
Simai He(smhe***at***se.cuhk.edu.hk)
Yinyu Ye(yinyu-ye***at***stanford.edu)
Zizhuo Wang(zzwang***at***stanford.edu)
Shuzhong Zhang(zhang***at***se.cuhk.edu.hk)

Abstract: This paper presents a general technique to develop approximation algorithms for allocation problems with integral assignment constraints. The core of the method is a randomized dependent rounding scheme, called geometric rounding, which yields termwise rounding ratios (in expectation), while emphasizing the strong correlation between events. We further explore the intrinsic geometric structure and general theoretical properties of this rounding scheme. First we will apply the geometric rounding algorithm(GRA) to solve a maximization problem, the winner determination problem(WDP) in a single-minded combinatorial auction. Its approximation ratio depends only on the maximal cardinality of the preferred bundles of players. The algorithm also provides a similar bound for the multi-unit WDP by integrating the rounding scheme with a bin packing technique. We then develop a probabilistic analysis of the geometric rounding for minimization problems. The application of this analysis yields the first nontrivial approximation algorithm for the hub location problem. It also generates simple approximation algorithms for the set cover and non-metric uncapacitated facility location problems(UFLP).

Keywords: Integer programming; quadratic assignment; geometric rounding; randomized algorithm; approximation algorithm.

Category 1: Applications -- OR and Management Sciences

Category 2: Combinatorial Optimization (Approximation Algorithms )


Download: [PDF]

Entry Submitted: 04/14/2008
Entry Accepted: 04/15/2008
Entry Last Modified: 04/14/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society