Randomized Rounding in the Presence of a Cardinality Constraint

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

zbMATH Keywords

approximation algorithmsrandomized roundingalgorithm engineering

Mathematics Subject Classification ID

Approximation algorithms (68W25) Randomized algorithms (68W20)

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 L_p-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