  


Geometric Rounding: A Dependent Rounding Scheme for Allocation Problems
Dongdong Ge(dongdongstanford.edu) 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 singleminded 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 multiunit 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 nonmetric 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 ) Citation: Download: [PDF] Entry Submitted: 04/14/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  