Geometric rounding: A dependent randomized rounding scheme
From MaRDI portal
Publication:411220
DOI10.1007/s10878-010-9320-zzbMath1236.90081MaRDI 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
90C10: Integer programming
90C05: Linear programming
90C59: Approximation methods and heuristics in mathematical programming
Related Items
Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem, An improved algorithm for fixed-hub single allocation problems, Approximation algorithms for median hub location problems
Cites Work
- Unnamed Item
- 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
- 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
