An alternative proof for the constructive Asymmetric Lovász Local Lemma

Ioannis Giotis; Lefteris Kirousis; Kostas I. Psaromiligkos; Dimitrios M. Thilikos

Retour

An alternative proof for the constructive Asymmetric Lovász Local Lemma

Acte de colloque

Open Access

An alternative proof for the constructive Asymmetric Lovász Local Lemma

Ioannis Giotis, Lefteris Kirousis, Kostas I. Psaromiligkos et Dimitrios M. Thilikos

13th Cologne-Twente Workshop on Graphs & Combinatorial Optimization

CTW: Cologne-Twente Workshop on Graphs and Combinatorial Optimization (İstanbul, Turkey, 26/05/2015–28/05/2015)

2015

Résumé

We provide an alternative constructive proof of the Asymmetric Lovász Local Lemma. Our proof uses the classic algorithmic framework of Moser and the analysis introduced by Giotis, Kirousis, Psaromiligkos, and Thilikos in " On the algorithmic Lovász Local Lemma and acyclic edge coloring " , combined with the work of Bender and Richmond on the multivariable Lagrange Inversion formula.

Fichiers et liens (1)

url

Find in HALAfficher

Indicateurs

1 Consultations de la notice

Détails

Titre: An alternative proof for the constructive Asymmetric Lovász Local Lemma
Créateurs - sans rôle: Ioannis Giotis - Computer Technology Institute and Press “DIOPHANTUS”
Lefteris Kirousis - Computer Technology Institute and Press “DIOPHANTUS”
Kostas I. Psaromiligkos - Department of Mathematics [Athens]
Dimitrios M. Thilikos - Computer Technology Institute and Press “DIOPHANTUS”
Détails de publication: 13th Cologne-Twente Workshop on Graphs & Combinatorial Optimization
Colloque: CTW: Cologne-Twente Workshop on Graphs and Combinatorial Optimization (İstanbul, Turkey, 26/05/2015–28/05/2015)
Identifiants: 9944667409311
Unité académique: Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier - LIRMM
Langue: English
Type de ressource: Conference proceeding
Champs locaux: lirmm-01370328