Randomized Rounding in the Presence of a Cardinality Constraint
From MaRDI portal
Publication:2828177
DOI10.1145/2594409zbMath1347.68361OpenAlexW1973343848MaRDI QIDQ2828177
Benjamin Doerr, Magnus Wahlström
Publication date: 24 October 2016
Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2594409
Related Items
Provable randomized rounding for minimum-similarity diversification ⋮ A closest vector problem arising in radiation therapy planning
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Multiterminal global routing: A deterministic approximation scheme
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
- Design and analysis of randomized algorithms. Introduction to design paradigms.
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Covering Problems with Hard Capacities
- A unified approach to scheduling on unrelated parallel machines
- Dependent rounding and its applications to approximation algorithms
- Matrix Rounding under the Lp-Discrepancy Measure and Its Application to Digital Halftoning
- Nonindependent Randomized Rounding and an Application to Digital Halftoning
- Randomized Rounding in the Presence of a Cardinality Constraint
- Dependent Randomized Rounding: The Bipartite Case
- Generating Randomized Roundings with Cardinality Constraints and Derandomizations
- STACS 2005
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems