Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Engineering a Lightweight and Efficient Local Search SAT Solver Read chapter Read first chapter

2016 | OriginalPaper | Chapter

How to Generate Randomized Roundings with Dependencies and How to Derandomize Them

Authors : Benjamin Doerr, Magnus Wahlström

Published in: Algorithm Engineering

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We give a brief survey on how to generate randomized roundings that satisfy certain constraints with probability one and how to compute roundings of comparable quality deterministically (derandomized randomized roundings). The focus of this treatment of this broad topic is on how to actually compute these randomized and derandomized roundings and how the different algorithms with similar proven performance guarantees compare in experiments and the applications of computing low-discrepancy point sets, low-congestion routing, the max-coverage problem in hypergraphs, and broadcast scheduling. While mostly surveying results of the last 5 years, we also give a simple, unified proof for the correctness of the different dependent randomized rounding approaches.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Recent Advances in Graph Partitioning
next chapter External-Memory State Space Search
Footnotes
1
Note that some earlier solutions for special cases exist, e.g., for sums of variables adding up to one [47] or the hypergraph discrepancy problem [14, 15], which is the rounding problem with all variables being 1 / 2 and the rounding errors defined by a binary matrix.
 
2
Note that, in fact, \(E[y]=x\) and \(y \in \{\lfloor x \rfloor , \lceil x \rceil \}\) is equivalent to saying that y is a randomized rounding of x.
 
Literature
1.
Ageev, A.A., Sviridenko, M.: Pipage rounding: a new method of constructing algorithms with proven performance guarantee. J. Comb. Optim. 8(3), 307–328 (2004)MathSciNetCrossRefMATH
2.
Al-Karaki, J.N., Kamal, A.E.: Routing techniques in wireless sensor networks: a survey. Wirel. Commun. IEEE 11(6), 6–28 (2004)CrossRef
3.
Arora, S., Rao, S., Vazirani, U.V.: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2) (2009)
4.
Asadpour, A., Goemans, M.X., Madry, A., Gharan, S.O., Saberi, A.: An O(log n/ log log n)-approximation algorithm for the asymmetric traveling salesman problem. In: SODA, pp. 379–389 (2010)
5.
Bansal, N.: Constructive algorithms for discrepancy minimization. In: FOCS, pp. 3–10 (2010)
6.
7.
8.
9.
Chekuri, C., Vondrák, J., Zenklusen, R.: Dependent randomized rounding via exchange properties of combinatorial structures. In: FOCS, pp. 575–584 (2010)
10.
Chekuri, C., Vondrák, J., Zenklusen, R.: Multi-budgeted matchings and matroid intersection via dependent rounding. In: SODA, pp. 1080–1097 (2011)
11.
12.
Demers, A.J., Greene, D.H., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H.E., Swinehart, D.C., Terry, D.B.: Epidemic algorithms for replicated database maintenance. Oper. Syst. Rev. 22, 8–32 (1988)CrossRef
13.
Dobkin, D.P., Eppstein, D., Mitchell, D.P.: Computing the discrepancy with applications to supersampling patterns. ACM Trans. Graph. 15(4), 354–376 (1996)CrossRef
14.
Doerr, B.: Multi-color discrepancies. dissertation, Christian-Albrechts-Universität zu Kiel (2000)
15.
16.
Doerr, B.: Generating randomized roundings with cardinality constraints and derandomizations. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 571–583. Springer, Heidelberg (2006). doi:10.​1007/​11672142_​47 CrossRef
17.
18.
Doerr, B., Fouz, M., Friedrich, T.: Social networks spread rumors in sublogarithmic time. In: STOC, pp. 21–30. ACM (2011)
19.
Doerr, B., Fouz, M., Friedrich, T.: Experimental analysis of rumor spreading in social networks. In: MedAlg, pp. 159–173 (2012)
20.
Doerr, B., Fouz, M., Friedrich, T.: Why rumors spread so quickly in social networks. Communun. ACM 55, 70–75 (2012)CrossRef
21.
Doerr, B., Friedrich, T., Künnemann, M., Sauerwald, T.: Quasirandom rumor spreading: an experimental analysis. JEA 16. Article 3.3 (2011)
22.
Doerr, B., Gnewuch, M.: Construction of low-discrepancy point sets of small size by bracketing covers and dependent randomized rounding. In: Keller, A., Heinrich, S., Niederreiter, H. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2006, pp. 299–312. Springer, Heidelberg (2008)CrossRef
23.
Doerr, B.: Non-independent randomized rounding. In: SODA, pp. 506–507 (2003)
24.
Doerr, B., Friedrich, T., Sauerwald, T.: Quasirandom rumor spreading. In: SODA, pp. 773–781 (2008)
25.
Doerr, B., Friedrich, T., Sauerwald, T.: Quasirandom rumor spreading: expanders, push vs. pull, and robustness. In: ICALP, pp. 366–377 (2009)
26.
Doerr, B., Gnewuch, M., Kritzer, P., Pillichshammer, F.: Component-by-component construction of low-discrepancy point sets of small size. Monte Carlo Meth. Appl. 14(2), 129–149 (2008)MathSciNetCrossRefMATH
27.
Doerr, B., Gnewuch, M., Wahlström, M.: Implementation of a component-by-component algorithm to generate small low-discrepancy samples. In: L’Ecuyer, P., Owen, A.B. (eds.) Monte Carlo and Quasi-Monte Carlo Methods 2008, pp. 323–338. Springer, Heidelberg (2009)CrossRef
28.
Doerr, B., Gnewuch, M., Wahlström, M.: Algorithmic construction of low-discrepancy point sets via dependent randomized rounding. J. Complex. 26(5), 490–507 (2010)MathSciNetCrossRefMATH
29.
Doerr, B., Künnemann, M., Wahlström, M.: Randomized rounding for routing and covering problems: experiments and improvements. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 190–201. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-13193-6_​17 CrossRef
30.
Doerr, B., Künnemann, M., Wahlström, M.: Dependent randomized rounding: the bipartite case. In: ALENEX, pp. 96–106 (2011)
31.
Doerr, B., Wahlström, M.: Randomized rounding in the presence of a cardinality constraint. In: ALENEX, pp. 162–174 (2009)
32.
33.
Fleischer, L., Jain, K., Williamson, D.P.: Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. J. Comput. Syst. Sci. 72(5), 838–867 (2006)MathSciNetCrossRefMATH
34.
Gabow, H.N., Manu, K.S.: Packing algorithms for arborescences (and spanning trees) in capacitated graphs. Math. Program. 82, 83–109 (1998)MathSciNetMATH
35.
Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding in bipartite graphs. In: FOCS, pp. 323–332 (2002)
36.
Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding and its applications to approximation algorithms. J. ACM 53, 324–360 (2006)MathSciNetCrossRefMATH
37.
Giannopoulos, P., Knauer, C., Wahlström, M., Werner, D.: Hardness of discrepancy computation and epsilon-net verification in high dimension. J. Complexity 28(2), 162–176 (2012)MathSciNetCrossRefMATH
38.
Gnewuch, M., Wahlström, M., Winzen, C.: A new randomized algorithm to approximate the star discrepancy based on threshold accepting. SIAM J. Numerical Anal. 50(2), 781–807 (2012)MathSciNetCrossRefMATH
39.
Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115–1145 (1995)MathSciNetCrossRefMATH
40.
Hromkovič, J.: Design and Analysis of Randomized Algorithms. Introduction to Design Paradigms. Texts in Theoretical Computer Science An EATCS Series. Springer, Berlin (2005)CrossRefMATH
41.
42.
Moser, R.A., Tardos, G.: A constructive proof of the general Lovász local lemma. J. ACM 57(2) (2010)
43.
Niederreiter, H.: Random number generation and Quasi-Monte Carlo methods. In: CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (1992)
44.
Orlin, J.B.: Max flows in O(nm) time, or better. In: STOC, pp. 765–774 (2013)
45.
Oxley, J.: Matroid Theory. Oxford Graduate Texts in Mathematics. OUP Oxford, Oxford (2011)
46.
Panconesi, A., Srinivasan, A.: Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds. SIAM J. Comput. 26, 350–368 (1997)MathSciNetCrossRefMATH
47.
Raghavan, P.: Probabilistic construction of deterministic algorithms: approximating packing integer programs. J. Comput. Syst. Sci. 37, 130–143 (1988)MathSciNetCrossRefMATH
48.
Raghavan, P., Thompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7, 365–374 (1987)MathSciNetCrossRefMATH
49.
Raghavendra, P.: Optimal algorithms and inapproximability results for every CSP? In: STOC, pp. 245–254 (2008)
50.
Raghavendra, P., Steurer, D.: How to round any CSP. In: FOCS, pp. 586–594 (2009)
51.
Rothvoß, T.: The entropy rounding method in approximation algorithms. In: SODA, pp. 356–372 (2012)
52.
Saha, B., Srinivasan, A.: A new approximation technique for resource-allocation problems. In: ICS, pp. 342–357 (2010)
53.
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, vol. 24. Springer, Heidelberg (2003)MATH
54.
55.
Spencer, J.: Ten Lectures on the Probabilistic Method. SIAM, Philadelphia (1987)MATH
56.
Srinivasan, A.: Distributions on level-sets with applications to approximations algorithms. In: FOCS, pp. 588–597 (2001)
57.
Srivastav, A., Stangier, P.: Algorithmic Chernoff-Hoeffding inequalities in integer programming. Random Struct. Algorithms 8, 27–58 (1996)MathSciNetCrossRefMATH
58.
Szegedy, M.: The Lovász local lemma - a survey. In: CSR, pp. 1–11 (2013)
Metadata
Title
How to Generate Randomized Roundings with Dependencies and How to Derandomize Them
Authors
Benjamin Doerr
Magnus Wahlström
Copyright Year
2016
Book
Algorithm Engineering

Print ISBN: 978-3-319-49486-9

Electronic ISBN: 978-3-319-49487-6

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-49487-6_5

Premium Partner

    Image Credits