On the power of random greedy algorithms

DOI10.1016/J.EJC.2022.103551zbMATH Open1491.05111arXiv2104.07854OpenAlexW3153696349MaRDI QIDQ2145759FDOQ2145759

He Guo, Lutz Warnke

Publication date: 20 June 2022

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: In this paper we solve two problems of Esperet, Kang and Thomasse as well as Li concerning (i) induced bipartite subgraphs in triangle-free graphs and (ii) van der Waerden numbers. Each time random greedy algorithms allow us to go beyond the Lovasz Local Lemma or alteration method used in previous work, illustrating the power of the algorithmic approach to the probabilistic method.

Full work available at URL: https://arxiv.org/abs/2104.07854

zbMATH Keywords

probabilistic methodalgorithmic approach

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On a packing and covering problem
• A new proof of Szemerédi's theorem
• How to make a graph bipartite
• The triangle-free process
• The Ramsey number R(3, t) has order of magnitude t²/log t
• A note on the random greedy independent set algorithm
• The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘)
• The early evolution of the \(H\)-free process
• Differential equations for random processes and random graphs
• The Final Size of the $C_{\ell}$-free Process
• When does the K₄‐free process stop?
• The C_ℓ‐free process
• A Note on Elkin’s Improvement of Behrend’s Construction
• A lower bound for off-diagonal van der Waerden numbers
• Arithmetic progressions in sumsets
• Asymptotically good list-colorings
• A subexponential upper bound for van der Waerden numbers \(W(3,k)\)
• Asymptotic packing via a branching process
• Bipartite induced density in triangle-free graphs
• Dense induced bipartite subgraphs in triangle-free graphs
• Packing nearly optimal Ramsey \(R(3,t)\) graphs
• Separation Choosability and Dense Bipartite Induced Subgraphs
• On a conjecture of Erdős on locally sparse Steiner triple systems
• On the missing log in upper tail estimates
• Large girth approximate Steiner triple systems
• Dynamic concentration of the triangle‐free process

Cited In (7)

• On the Power of the Randomized Iterate
• An almost-greedy search on random binary vectors and random graphs
• On randomizing two derandomized greedy algorithms
• On randomized sketching algorithms and the Tracy-Widom law
• Stochastic analysis of greedy algorithms for the subset sum problem
• Bounds on Ramsey games via alterations
• Title not available (Why is that?)

Recommendations

• On the power of randomization in on-line algorithms 👍 👎
• Some remarks on greedy algorithms 👍 👎
• A note on the random greedy independent set algorithm 👍 👎
• On the greedy algorithm with random costs 👍 👎
• On randomizing two derandomized greedy algorithms 👍 👎
• On the Power of the Randomized Iterate 👍 👎
• On the Power of the Randomized Iterate 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: On the power of random greedy algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2145759)