Geometric rounding: A dependent randomized rounding scheme
From MaRDI portal
Publication:411220
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
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
