Geometric rounding: a dependent randomized rounding scheme

Dongdong Ge (), Simai He (), Yinyu Ye () and Jiawei Zhang ()
Additional contact information
Dongdong Ge: Shanghai Jiao Tong University
Simai He: The Chinese University of Hong Kong
Yinyu Ye: Stanford University
Jiawei Zhang: New York University

Journal of Combinatorial Optimization, 2011, vol. 22, issue 4, No 17, 699-725

Abstract: Abstract 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 (J. ACM 49(5):616–639, 2002) and its variants is also conducted. Overall, our geometric rounding provides a simple and effective alternative for rounding various integer optimization problems.

Keywords: Integer programming; Linear programming; Approximation algorithm; Randomized rounding (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-010-9320-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:22:y:2011:i:4:d:10.1007_s10878-010-9320-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-010-9320-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().