Randomized rounding

Network Optimization Techniques

Published in Erchin Serpedin, Thomas Chen, Dinesh Rajan, Mathematical Foundations for SIGNAL PROCESSING, COMMUNICATIONS, AND NETWORKING, 2012

Michał Pióro

In branch-and-bound it is important to systematically compute good upper bounds for the optimal solutions in the nodes of the BB tree. One such approach is called “randomized rounding” and was proposed by P. Raghavan and C. Thompson in [66]. Randomized rounding is a probabilistic method in the sense that the procedure yields random approximate solutions of a 0–1 integer problem.

Improved Approximation Algorithm for the Fault-Tolerant Facility Placement Problem with Rejection

View Article

Journal Information

Published in American Journal of Mathematical and Management Sciences, 2020

Shuaijing Yu

In this article, we revisit the fault-tolerant facility placement problem with rejection. By adopting a randomized rounding approach and the derandomizing technique, we propose an improved approximation algorithm with performance ratio of 2.07 compared to the currently best approximation algorithm with performance ratio of 2.515 due to Fang and Luo (2016). It will be interesting to further improve the performance ratio for the FTFPWR.

Randomized rounding

Explore chapters and articles related to this topic

Network Optimization Techniques

Improved Approximation Algorithm for the Fault-Tolerant Facility Placement Problem with Rejection