Abstract
We provide a general method to generate randomized roundings that satisfy cardinality constraints. Our approach is different from the one taken by Srinivasan (FOCS 2001) and Gandhi et al. (FOCS 2002) for one global constraint and the bipartite edge weight rounding problem.
Also for these special cases, our approach is the first that can be derandomized. For the bipartite edge weight rounding problem, in addition, we gain an \(\tilde{O}(|V|)\) factor run-time improvement for generating the randomized solution.
We also improve the current best result on the general problem of derandomizing randomized roundings. Here we obtain a simple O(mnlog n) time algorithm that works in the RAM model for arbitrary matrices with entries in ℚ ≥ 0. This improves over the O(mn 2 log(mn)) time solution of Srivastav and Stangier.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arora, S., Frieze, A., Kaplan, H.: A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. Math. Program. 92, 1–36 (2002)
Asano, T., Katoh, N., Obokata, K., Tokuyama, T.: Matrix rounding under the \(L\sb p\)-discrepancy measure and its application to digital halftoning. SIAM J. Comput. 32, 1423–1435 (2003)
Ageev, A.A., Sviridenko, M.I.: Pipage rounding: a new method of constructing algorithms with proven performance guarantee. J. Comb. Optim. 8, 307–328 (2004)
Beck, J., Spencer, J.: Integral approximation sequences. Math. Programming 30, 88–98 (1984)
Doerr, B.: Non-independent randomized rounding. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 506–507 (2003)
Doerr, B.: Nonindependent randomized rounding and an application to digital halftoning. SIAM Journal on Computing 34, 299–317 (2004)
Doerr, B.: Roundings respecting hard constraints. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 617–628. Springer, Heidelberg (2005)
Gandhi, R., Halperin, E., Khuller, S., Kortsarz, G., Srinivasan, A.: An improved approximation algorithm for vertex cover with hard capacities. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 164–175. Springer, Heidelberg (2003)
Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding in bipartite graphs. In: Proc. IEEE Symposium on Foundations of Computer Science (FOCS), pp. 323–332 (2002)
Guruswami, V., Khanna, S., Rajaraman, R., Shepherd, B., Yannakakis, M.: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. In: Annual ACM Symposium on Theory of Computing (STOC), pp. 19–28. ACM, New York (1999)
Panconesi, A., Srinivasan, A.: Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds. SIAM J. Comput. 26, 350–368 (1997)
Raghavan, P.: Probabilistic construction of deterministic algorithms: Approximating packing integer programs. J. Comput. Syst. Sci. 37, 130–143 (1988)
Raghavan, P., Thompson, C.D.: Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica 7, 365–374 (1987)
Raghavan, P., Thompson, C.D.: Multiterminal global routing: a deterministic approximation scheme. Algorithmica 6, 73–82 (1991)
Spencer, J.: Ten lectures on the probabilistic method. In: CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics, vol. 64, SIAM, Philadelphia (1994)
Srinivasan, A.: Distributions on level-sets with applications to approximations algorithms. In: Proc. 41th Ann. IEEE Symp. on Foundations of Computer Science (FOCS), pp. 588–597 (2001)
Srivastav, A., Stangier, P.: Algorithmic Chernoff-Hoeffding inequalities in integer programming. Random Structures & Algorithms 8, 27–58 (1996)
Sadakane, K., Takki-Chebihi, N., Tokuyama, T.: Combinatorics and algorithms on low-discrepancy roundings of a real sequence. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Doerr, B. (2006). Generating Randomized Roundings with Cardinality Constraints and Derandomizations. In: Durand, B., Thomas, W. (eds) STACS 2006. STACS 2006. Lecture Notes in Computer Science, vol 3884. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11672142_47
Download citation
DOI: https://doi.org/10.1007/11672142_47
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32301-3
Online ISBN: 978-3-540-32288-7
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science