Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Engineering a Lightweight and Efficient Local Search SAT Solver Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

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

verfasst von : Benjamin Doerr, Magnus Wahlström

Erschienen in: Algorithm Engineering

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Recent Advances in Graph Partitioning
Nächstes Kapitel External-Memory State Space Search
Fußnoten
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.
 
Literatur
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.
Doerr, B.: Randomly rounding rationals with cardinality constraints and derandomizations. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 441–452. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-70918-3_​38 CrossRef
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.
Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21(1), 39–60 (2001)MathSciNetCrossRefMATH
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)
Metadaten
Titel
How to Generate Randomized Roundings with Dependencies and How to Derandomize Them
verfasst von
Benjamin Doerr
Magnus Wahlström
Copyright-Jahr
2016
Buch
Algorithm Engineering

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

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

Copyright-Jahr: 2016

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

Premium Partner

    Bildnachweise