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

Recommendations

• On the greedy algorithm with random costs
• On randomizing two derandomized greedy algorithms
• Randomized greedy: new variants of some classic approximation algorithms
• On the power of randomization in on-line algorithms
• A note on the random greedy independent set algorithm
• scientific article; zbMATH DE number 1875441
• On the Power of the Randomized Iterate
• On the Power of the Randomized Iterate
• scientific article; zbMATH DE number 3970528
• Some remarks on greedy algorithms

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?)
• 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)\)
• On the growth of a van der Waerden-like function
• 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?)

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)