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:
On the Push&Pull Protocol for Rumour Spreading Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

An Alternate Proof of the Algorithmic Lovász Local Lemma

verfasst von : Ioannis Giotis, Lefteris Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos

Erschienen in: Extended Abstracts Summer 2015

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The algorithm for Lovász Local Lemma by Moser and Tardos gives a constructive way to prove the existence of combinatorial objects satisfying a system of constraints. We present an alternative probabilistic analysis of the algorithm that does not involve reconstructing the history of the algorithm. We apply our technique to improve the best known upper bound to acyclic chromatic index.

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 Approximation Algorithms for Computing Maximin Share Allocations
Nächstes Kapitel Learning Game-Theoretic Equilibria Via Query Protocols
Fußnoten
1
The algorithm in [8] was presented and analyzed only for the sat problem, whereas the one in [9] was presented and analyzed in a general setting; the generalization of the algorithm in  [8] for arbitrary events is straightforward; however, the analysis in [8] does not immediately generalize.
 
Literatur
1.
N. Alon, “A parallel algorithmic version of the local lemma”, Random Structures & Algorithms 2 (4) (1991), 367–378.
2.
J. Beck, “An algorithmic approach to the Lovász local lemma, I”, Random Structures & Algorithms 2 (4) (1991), 343–365.
3.
P. Erdős and L. Lovász, “Problems and results on 3-chromatic hypergraphs and some related questions”, Infinite and finite sets 10 (1975), 609–627.
4.
5.
I. Giotis, L. Kirousis, K.I. Psaromiligkos, and D.M. Thilikos, “An alternative proof for the constructive asymmetric Lovász local lemma”, presented at the 13-th Twente-Cologne Workshop on Graphs & Combinatorial Optimization, 2015, Istanbul.
6.
D.E. Knuth, “Stable marriage and its relation to other combinatorial problems: an introduction to the mathematical analysis of algorithms”, volume 10, American Mathematical Soc., 1997.
7.
K.B.R. Kolipaka and M. Szegedy, “Moser and Tardos meet Lováz”, Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC ’11 (2011), 235–244.
8.
R.A. Moser, “A constructive proof of the Lovász Local Lemma”, Proceedings of the 41-st annual ACM Symposium on Theory of Computing (2009), 343–350.
9.
R.A. Moser and G. Tardos, “A constructive proof of the general Lovász Local Lemma”, Journal of the ACM (JACM) 57 (2) (2010), 11.
10.
11.
A. Srinivasan, “Improved algorithmic versions of the Lovász Local Lemma”, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (Society for Industrial and Applied Mathematics) (2008), 611–620.
12.
M. Szegedy, “The Lovász local lemma —a survey”, Computer Science–Theory and Applications (2013), 1–11, Springer, Berlin/Heidelberg.
13.
Metadaten
Titel
An Alternate Proof of the Algorithmic Lovász Local Lemma
verfasst von
Ioannis Giotis
Lefteris Kirousis
Kostas I. Psaromiligkos
Dimitrios M. Thilikos
Copyright-Jahr
2017
Buch
Extended Abstracts Summer 2015

Print ISBN: 978-3-319-51752-0

Electronic ISBN: 978-3-319-51753-7

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-51753-7_10