Geometric rounding: A dependent randomized rounding scheme

DOI10.1007/s10878-010-9320-zzbMath1236.90081OpenAlexW1994294861MaRDI QIDQ411220

Yinyu Ye, Simai He, Jia-Wei Zhang, Dong-Dong Ge

Publication date: 4 April 2012

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-010-9320-z

zbMATH Keywords

linear programminginteger programmingapproximation algorithmrandomized rounding

Mathematics Subject Classification ID

Integer programming (90C10) Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem, A parameterized approximation algorithm for the multiple allocation \(k\)-hub center, Approximation algorithms for median hub location problems, An improved algorithm for fixed-hub single allocation problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• On dependent randomized rounding algorithms
• An approximation algorithm for the generalized assignment problem
• Rounding algorithms for covering problems
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• A threshold of ln n for approximating set cover
• Approximation algorithms for classification problems with pairwise relationships
• Dependent rounding and its applications to approximation algorithms
• Approximation algorithms for combinatorial auctions with complement-free bidders
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Analysis of LP relaxations for multiway and multicut problems
• Hub Location and the p-Hub Median Problem
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Lower Bounds for the Hub Location Problem