Geometric rounding: A dependent randomized rounding scheme

DOI10.1007/S10878-010-9320-ZMaRDI QIDQ411220zbMATH OpenOpenAlexFDO

Authors Simai He, Yinyu Ye, Dongdong Ge, Jiawei Zhang

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 programmingapproximation algorithminteger programmingrandomized rounding

Mathematics Subject Classification ID

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

Recommendations

• On dependent randomized rounding algorithms
• Dependent rounding and its applications to approximation algorithms
• scientific article; zbMATH DE number 2079377
• Dependent Randomized Rounding: The Bipartite Case
• Correlated Rounding of Multiple Uniform Matroids and Multi-Label Classification

Cites work

• scientific article; zbMATH DE number 5764821 (Why is no real title available?)
• scientific article; zbMATH DE number 3954145 (Why is no real title available?)
• scientific article; zbMATH DE number 1182757 (Why is no real title available?)
• scientific article; zbMATH DE number 2079339 (Why is no real title available?)
• scientific article; zbMATH DE number 1775387 (Why is no real title available?)
• scientific article; zbMATH DE number 871894 (Why is no real title available?)
• A threshold of ln n for approximating set cover
• An approximation algorithm for the generalized assignment problem
• Analysis of LP relaxations for multiway and multicut problems
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
• Approximation algorithms for combinatorial auctions with complement-free bidders
• Approximation algorithms for the metric labeling problem via a new linear programming formulation
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Dependent rounding and its applications to approximation algorithms
• Hub Location and the p-Hub Median Problem
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Introduction to probability models
• Lower Bounds for the Hub Location Problem
• On dependent randomized rounding algorithms
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Rounding algorithms for covering problems

Cited in

(7)

• A parameterized approximation algorithm for the multiple allocation \(k\)-hub center
• Simplex partitioning via exponential clocks and the multiway-cut problem
• Dependent Randomized Rounding: The Bipartite Case
• An improved algorithm for fixed-hub single allocation problems
• Approximation algorithms for median hub location problems
• Dependent rounding and its applications to approximation algorithms
• scientific article; zbMATH DE number 2079377 (Why is no real title available?)

This page was built for publication: Geometric rounding: A dependent randomized rounding scheme

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q411220)